LeetCode Swap Nodes in Pairs：鏈表成對交換遞歸與迭代解法

問題描述

給定單鏈表，將相鄰節點成對交換，返回新頭節點。要求 O(1) 額外空間，不可修改節點值，只能調整指針。
例如：1→2→3→4 → 2→1→4→3。

遞歸解法（最直觀）

基本情況：head == nullptr 或 head->next == nullptr，直接返回 head。
遞歸步驟：

1. newHead = head->next（第二個節點將成為新頭）
2. nextPair = newHead->next（第三個節點，下一組的頭）
3. newHead->next = head（完成本組交換）
4. head->next = swapPairs(nextPair)（遞歸處理剩餘）
5. 返回 newHead

// Java 版
public ListNode swapPairs(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return head;
    ListNode newHead = head.next;
    ListNode nextPair = head.next.next;
    newHead.next = head;
    head.next = swapPairs(nextPair);
    return newHead;
}

迭代解法（O(1) 空間，無棧溢出風險）

使用虛擬頭節點 dummy 簡化邊界處理，維護 prev 指向已處理部分的尾節點。

// C++ 版
ListNode* swapPairs(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    while (prev->next && prev->next->next) {
        ListNode* first = prev->next;
        ListNode* second = first->next;
        ListNode* nextPair = second->next;

        prev->next = second;
        second->next = first;
        first->next = nextPair;

        prev = first; // first 現為本組尾部
    }
    return dummy.next;
}

關鍵點對比

常見錯誤

• 忘記保存 nextPair 導致鏈表斷裂。
• 交換後 prev 更新錯誤（應移至原 first，即現尾節點）。
• 未處理 head==nullptr 或單節點情況。

總結

Swap Nodes in Pairs 是鏈表指針操作基礎題。遞歸寫法適合面試快速表達思路；迭代寫法是工程級首選。掌握「虛擬頭節點 + 三指針（prev, first, second）+ 保存下一組頭」模式，可輕鬆擴展到 K 組翻轉等變體。