題目

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

解題概念

  • 題意 : 給定 Singly Linked List 的 head，需要回傳 Singly Linked List 的 中間節點
  • 若有兩個中間節點，則返回第二個中間節點

我的寫法

  • 想法 : 採用 雙重指標
    • 讓 ptr 一次走一步
    • 讓 qtr 一次走兩步
    • 當 qtr 走到底時，ptr.next 即為中間節點
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def middleNode(self, head):
        
        if not head.next : return head
        ptr = head
        qtr = head.next
        
        while qtr and qtr.next and qtr.next.next:
            ptr = ptr.next
            qtr = qtr.next.next

        return ptr.next
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 187 ms (faster than 5.40%)
    • Memory Usage: 13.7 MB (more than 18.26%)

解答 or 其他優秀寫法

  • 想法 : 與我的寫法大致相同，但寫得更為乾淨
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    ef middleNode(self, head):
       
        ptr = head
        qtr = head
        
        while qtr and qtr.next:
            ptr = ptr.next
            qtr = qtr.next.next

        return ptr
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 17 ms (faster than 53.04%)
    • Memory Usage: 13.47 MB (more than 18.26%)