LeetCode Reorder List：鏈表重排 L0→Ln→L1→Ln-1...

問題描述

給定單鏈表 L0→L1→...→Ln-1→Ln，原地重排為 L0→Ln→L1→Ln-1→L2→Ln-2→...。不允許修改節點值，只能改指針。

算法三步走

1. 找中點：快慢指針，slow 走一步，fast 走兩步。停時 slow 在中點（奇數長度偏左）。
2. 反轉後半部分鏈表：從 slow->next 開始反轉，slow->next = nullptr 斷開。
3. 合併兩鏈表：交替穿針，first->next = second; second->next = first->next...

代碼實現

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        // 1. 找中點
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 2. 反轉後半段
        ListNode *prev = nullptr, *curr = slow->next;
        slow->next = nullptr;
        while (curr) {
            ListNode *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        // 3. 合併
        ListNode *first = head, *second = prev;
        while (second) {
            ListNode *tmp1 = first->next;
            ListNode *tmp2 = second->next;
            first->next = second;
            second->next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
};

關鍵細節

• 中點判定：fast->next && fast->next->next 保證奇數長度時前半段多一個節點（如 1-2-3-4-5 → 前半 1-2-3，後半 4-5 反轉為 5-4）。
• 合併時 second 為短鏈表（或等長），以 second 為循環條件。
• 全程只改指針，不創建新節點，滿足原地要求。

複雜度

• 時間：O(n) 三次遍歷（找中點、反轉、合併）。
• 空間：O(1) 僅用常數指針變量。

圖解過程

原始: 1 → 2 → 3 → 4 → 5
中點: 1 → 2 → 3    4 → 5
反轉: 1 → 2 → 3    5 → 4
合併: 1 → 5 → 2 → 4 → 3

總結

Reorder List 是鏈表操作綜合訓練：快慢指針找中點、就地反轉、交替合併。三步各為經典子問題，組合起來考察指針操作熟練度。掌握此模板，鏈表重排、回文判斷、折疊等問題皆可迎刃而解。