876. Middle of the Linked List

──────────────────────────────────────────────────────────────────────

回傳鏈結串列的中間節點。節點數是偶數時，回傳後面那一個。

思路

鏈結串列沒有 len()，也不能用索引 —— 這就是這題的全部難點。

直覺解：數兩趟

先走一趟數出長度 n，再走 n // 2 步。一定寫得出來，而且很好解釋。缺點是走了兩趟。

一趟解：快慢指針

要一趟做完，關鍵是用相對速度取代絕對位置：

讓 fast 一次走兩步、slow 一次走一步。fast 走到底時，它走的距離是 slow 的兩倍 —— 所以 slow 剛好在一半的地方。

這個「兩倍速」的想法是鏈結串列題最重要的工具之一，因為串列不能隨機存取，唯一能拿到「相對位置」的方法就是讓兩個指針用不同的速度或起點走。

偶數長度時要回傳後面那個中點，這個版本剛好自動符合，不用特別處理 —— 下面解釋為什麼。

解題方向

數兩趟

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        count = 1
        while curr.next != None:
            curr = curr.next
            count += 1
        
        res = head
        count = count // 2
        while count > 0:
            count -= 1
            res = res.next

        return res

count 從 1 開始（把 head 自己算進去），所以迴圈條件是 curr.next != None 而不是 curr != None。這種「從 1 開始數、看下一個」的寫法很容易差一，如果不確定就從 0 開始、條件用 while curr，比較不會錯。

這版在 head 是 None 時會 AttributeError。LeetCode 保證至少 1 個節點所以不會踩到，但面試時可以主動提一句。

快慢指針

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

為什麼偶數長度時剛好回傳後面那個中點？ 因為迴圈條件是 while fast and fast.next：

長度 5（奇數）：fast 走到最後一顆時 fast.next 是 None，停下來，slow 在索引 2 —— 正中間。
長度 6（偶數）：fast 走出串列變成 None，停下來，slow 在索引 3 —— 也就是後面那個中點。

如果題目要的是前面那個中點（例如 143. Reorder List 需要把串列切兩半時），就把條件改成 while fast.next and fast.next.next。這兩個條件的差別就是「回傳哪個中點」，值得記住，因為切串列的題目對這個很敏感。

補充

快慢指針的其他用途：141. Linked List Cycle（有環時快的會追上慢的）、143. Reorder List（先找中點再反轉後半）、2095. Delete the Middle Node of a Linked List（要停在中點的前一個才能刪）、19. Remove Nth Node From End of List（改成讓快的先走 n 步）。

共同點都是「沒有索引，就用兩個指針的相對關係換出位置資訊」，整理見 Linked List 模板。

複雜度

數兩趟

時間 $O (n)$ — 走兩趟，仍然是線性
空間 $O (1)$

快慢指針

時間 $O (n)$ — 只走一趟，fast 走 $n / 2$ 次迴圈
空間 $O (1)$

其中 n 是節點數。兩者同級，快慢指針的好處是一趟解決，而且它是後面一整批串列題的基礎工具。