快慢指針題型

題目連結: 876. Middle of the Linked List

題目描述:給定一個單向鏈結串列的頭節點 head，請返回鏈結串列的 中間節點。
如果鏈結串列有兩個中間節點（即長度為偶數），則返回 第二個中間節點。

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Python

解題思路:

• 設定兩個指針，slow 與 fast，slow每次變化都是一步，fast則是兩步。
• fast 跑到終點時，slow 剛好會落在中間。

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
            
        return slow

演算法分析:

• 初始化 slow = head, fast = head。
• fast != None：處理長度為奇數的情況 (例如 1->2->3，fast 最後會停在 3)。
• fast.next != None：處理長度為偶數的情況 (例如 1->2->3->4，fast 最後會停在 3，此時 fast.next 是 4，下一輪 fast 會跑到 None 的外面去，所以要提前停止)。

複雜度分析:

• 雖然有兩個指針，但我們只對Linked List進行了一次完整的遍歷（以 fast 指針為準）。n 是鏈結串列的長度，時間複雜度為 O(n)。

• 空間複雜度： O(1)(我們只使用了 slow 和 fast 兩個額外的指針，沒有使用任何與Linked List長度相關的額外儲存空間)。

有問題可以底下留言!
下回見!!