LeetCode 24 Swap Nodes in Pairs - 兩兩交換鏈表節點

題目翻譯

給定單鏈表，每兩個相鄰節點交換位置，返回新頭節點。要求 O(1) 空間，只能修改指針不能修改值。例：1→2→3→4 → 2→1→4→3。

遞歸解法（最直觀）

將鏈表視為「前兩個節點」+「剩餘鏈表」。交換前兩個，然後遞歸處理剩餘，將結果接在原頭節點（現為第二個）後面。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* second = head->next;
        head->next = swapPairs(second->next);
        second->next = head;
        return second;
    }
};

迭代解法（O(1) 額外空間，無遞歸棧）

用虛擬頭節點 dummy，維護 pre 指向待交換對的前一個節點。每輪交換 pre->next 和 pre->next->next，然後推進 pre。

ListNode* swapPairs(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* pre = &dummy;

    while (pre->next && pre->next->next) {
        ListNode* a = pre->next;
        ListNode* b = a->next;
        // 交換 a 和 b
        pre->next = b;
        a->next = b->next;
        b->next = a;
        // 推進 pre 到 a（現為對尾）
        pre = a;
    }
    return dummy.next;
}

圖解交換過程

初始:  pre → a → b → rest
步驟1: pre → b
步驟2: a → rest
步驟3: b → a
結果:  pre → b → a → rest

複雜度

• 時間：O(n)
• 空間：遞歸 O(n) 棧；迭代 O(1)

總結

本題是鏈表指針操作基本功。「虛擬頭節點 + pre 指針」模式可套用於許多鏈表局部修改問題（如 K 組翻轉、刪除倒數第 N 個）。面試建議先寫遞歸版講清邏輯，再寫迭代版滿足空間要求。