LeetCode 鏈表專題總結：常見錯誤與核心技巧

鏈表操作四大常見錯誤

1. 空指針解引用：取 `val` 或 `next` 前未判空 → Runtime Error
2. 邊界條件遺漏：空鏈表、單節點、頭尾節點特殊處理
3. 斷鏈未置空：拆分/重組後尾節點 `next` 未設 `nullptr` → 形成環 → TLE/RE
4. 多指針更新順序錯誤：平移指針時順序顛倒 → 丟失節點或構成環

核心工具：O(N) 找中點 + 就地反轉

解決大部分鏈表重排、回文、合併問題的利器：

// 快慢指針找中點（前半段較長）
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
}

// 就地反轉（三指針法）
ListNode* reverse(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *pre = nullptr, *cur = head, *nxt;
    while (cur) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

實戰案例：Reorder List (LeetCode 143)

題目：`L0→L1→…→Ln-1→Ln` 重排為 `L0→Ln→L1→Ln-1→…`

1. 找中點 `mid`
2. 反轉後半段 `mid->next`
3. 斷開：`mid->next = nullptr`
4. 穿針引線合併兩段

合併邏輯關鍵代碼

ListNode *p1 = head, *p2 = reversed_head;
while (p2) {
    ListNode *tmp = p2->next;
    p2->next = p1->next;
    p1->next = p2;
    p1 = p1->next->next;  // 跳過剛插入的節點
    p2 = tmp;
}

避坑指南

• 反轉函數務必處理 `nullptr` 和單節點
• 合併時 `p1->next->next` 訪問前確保 `p1->next` 非空
• 調試時畫圖追蹤指針變化，切勿腦補
• 多寫幾遍反轉、找中點、合併模板，形成肌肉記憶

鏈表題核心在於指針操作的嚴謹性，掌握「找中點 + 反轉 + 合併」三板斧，配合邊界處理，可破解 80% 以上鏈表問題。