題目

  • 題目連結
  • 目標函式 : reverseList(head)
    • Input : head: ListNode
    • Output : ListNode

解題概念

  • 題意 : 給定一 Linked List head，需要將其反轉 (如下圖)

我的寫法

  • 想法 : 這題也是 Linked List 範疇中很經典的一題，可使用雙重指標來解題

    • 首先設定起始點 ptr 指向 None、qtr 指向 Node 1 (如圖)

    • 接著需依照此步驟去重複執行 (如圖) :

      1. temp = qtr.next : 找出下一個節點
      2. qtr.next : 將 qtr 指向節點的 next 指回 ptr
      3. ptr 做 shifting
      4. qtr 做 shifting

    • 直到 qtr 指向 None 時，代表已到終點。此時 ptr 就會指向新 Linked List 的起點，即可直接回傳

  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def reverseList(self, head):
        
        if not head: return None

        ptr = None
        qtr = head
        while qtr:
            temp = qtr.next
            qtr.next = ptr
            ptr = qtr
            qtr = temp
        return ptr
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 21 ms (faster than 67.51%)
    • Memory Usage: 15.26 MB (more than 66.39%)

解答 or 其他優秀寫法

  • 想法 : 改用 Recursion 之寫法，概念上與我的寫法相同，但在兩個指標 shifting 的部分改用 Recursion 去處理
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def reverse(self, qtr, ptr = None):
        if not qtr: return ptr

        temp = qtr.next # Step 1
        qtr.next = ptr # Step 2

        return self.reverse(temp, qtr) # 做 shifting (Step 3、4)

    def reverseList(self, head):
        
        return self.reverse(head)
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 17 ms (faster than 85.76%)
    • Memory Usage: 19.54 MB (more than 7.16%)