LeetCode 24 兩兩交換鏈表節點：指針操作圖解

問題描述

給定鏈表，每兩個相鄰節點交換位置。例如 1→2→3→4 → 2→1→4→3。需原地修改指針，不修改節點值。

核心思路：三指針操作交換相鄰對

使用哨兵節點 dummy，prev 指向待交換對的前一節點。每次交換 prev->next 和 prev->next->next。

逐步指針操作（以交換 a→b 為例）

// 交換前: prev → a → b → nextPair
ListNode* a = prev->next;
ListNode* b = a->next;
ListNode* nextPair = b->next;

// 1. prev → b
prev->next = b;
// 2. b → a
b->next = a;
// 3. a → nextPair
a->next = nextPair;

// 更新 prev 為 a (下一對的前一節點)
prev = a;

完整代碼 (C++)

ListNode* swapPairs(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    while (prev->next && prev->next->next) {
        ListNode* a = prev->next;
        ListNode* b = a->next;
        ListNode* nextPair = b->next;

        prev->next = b;
        b->next = a;
        a->next = nextPair;

        prev = a;
    }
    return dummy.next;
}

關鍵點

• 哨兵節點：統一處理頭節點交換。
• 保存 nextPair：斷開連接前必須保存後續鏈表，否則丟失。
• 指針順序：先連 prev→b，再 b→a，最後 a→nextPair。
• 循環條件：prev->next && prev->next->next 確保至少有兩個節點可交換。

複雜度分析

• 時間：O(n) — 單次遍歷。
• 空間：O(1) — 僅常數指針。

遞歸版本（補充）

ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* nextPair = head->next->next;
    ListNode* newHead = head->next;
    newHead->next = head;
    head->next = swapPairs(nextPair);
    return newHead;
}

總結

LeetCode 24 是鏈表指針操作基本功訓練。掌握「三節點交換指針重組」模板，可解決「K 個一組翻轉、隔節點交換」等變體。畫圖推導指針順序是避免錯誤的關鍵。