143. Reorder List

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

143. Reorder List

把 L0 → L1 → … → Ln-1 → Ln 重排成 L0 → Ln → L1 → Ln-1 → …，要原地做。

思路

想要的結果是「頭一個、尾一個、頭二個、尾二個…」交錯排列。如果是陣列，這題很簡單：左右各一個索引往中間收就好。但這是單向串列，拿不到「倒數第 k 個」—— 每次都要從頭走一遍找尾巴，那是 $O (n^{2})$ 。

關鍵轉念是：與其反覆去找尾巴，不如把後半段整條反轉過來。

反轉之後，「從尾巴往前走」就變成「從新的頭往後走」，兩條串列各自從頭往後走再交錯合併，就是 $O (n)$ 。

於是整題拆成三個都會的子問題：

找中點 —— 快慢指針，見 876. Middle of the Linked List
反轉後半 —— 見 206. Reverse Linked List
交錯合併 —— 兩條串列輪流接

這種「拆成三個已知子問題」的結構是這題被當作經典題的原因。面試時先講出這三步，再逐個實作，比直接埋頭寫穩得多。

切斷的那一刀很重要：找到中點後要把前半段的尾巴指向 None，否則反轉後前後兩段會互相指、形成環，交錯合併時會無限迴圈。

解題方向

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        slow = head
        fast = head

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

        # slow point to the middle point of the linked list

        def reverse(node):
            if not node or not node.next:
                return node
            last = reverse(node.next)
            node.next.next = node
            node.next = None
            return last

        r = reverse(slow.next)
        slow.next = None

        tmp = head
        while r:
            tmp_next = tmp.next
            r_next = r.next
            
            tmp.next = r        
            r.next = tmp_next
            
            tmp = tmp_next
            r = r_next
        
        return head

為什麼反轉的是 slow.next 而不是 slow？ 因為 slow 停在「後面那個中點」（見 876 的說明），它要留在前半段當結尾。反轉從它的下一顆開始，前半段就會比後半段多一顆或一樣多 —— 這正好是交錯合併需要的形狀（先放前半的元素，所以前半不能比後半短）。

交錯合併那段一定要先把兩邊的 next 存起來（tmp_next / r_next），因為 tmp.next = r 這行會立刻蓋掉 tmp 原本的下一顆。先存後改，是所有改指標題目的通則。

迴圈條件是 while r（後半段走完就停），因為前半段可能比後半段多一顆，那一顆的 next 已經在上一輪被正確接好了。

補充

遞迴版的 reverse 深度等於後半段的長度。 在 Python 預設的 recursionlimit = 1000 下，本機跑 n = 5000 就會 RecursionError（判題環境通常會調高）。

改成迭代版就沒有這個問題，而且更短：

        def reverse(node):
            prev = None
            while node:
                nxt = node.next
                node.next = prev
                prev = node
                node = nxt
            return prev

prev / node / nxt 三個指針往前滾，是反轉串列的標準寫法，而且沒有遞迴深度的顧慮。

函式簽名說 -> None，但這份程式碼回傳了 head。 題目要求原地修改、不回傳，多回傳一個值不會判錯，不過照著簽名寫比較嚴謹。

同一組工具的其他題：206. Reverse Linked List、92. Reverse Linked List II（只反轉中間一段）、876. Middle of the Linked List、148. Sort List（也是先找中點再切開）。整理見 Linked List 模板。

複雜度

時間 $O (n)$ — 找中點 $O (n)$ 、反轉後半 $O (n / 2)$ 、交錯合併 $O (n / 2)$ ，三個線性步驟相加
空間 $O (1)$ （迭代版反轉）或 $O (n)$ （遞迴版反轉，堆疊深度等於後半段長度）

其中 n 是節點數。全程只改指標、沒有建新節點，所以迭代版是真正的原地重排。