LeetCode 24：兩兩交換鏈表節點

題目：給定單鏈表，每兩個相鄰節點交換位置，返回新頭節點。如 1->2->3->4 變為 2->1->4->3。

方法一：迭代法（虛擬頭節點）

引入 dummy 指向 head，prev 指向待交換對的前一節點，cur 指向對中第一個節點。循環條件 cur && cur->next。交換步驟：

1. prev->next = cur->next（prev 指向第二個節點）
2. cur->next = cur->next->next（第一個節點指向下一對）
3. prev->next->next = cur（第二個節點指向第一個）
4. 更新 prev = cur; cur = cur->next 進入下一對。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *prev = dummy, *cur = head;
        while (cur && cur->next) {
            prev->next = cur->next;
            cur->next = cur->next->next;
            prev->next->next = cur;
            prev = cur;
            cur = cur->next;
        }
        return dummy->next;
    }
};

方法二：遞歸法

基礎情況：head == nullptr 或 head->next == nullptr 直接返回。否則：

1. tmp = head->next 保存第二個節點。
2. head->next = swapPairs(tmp->next) 遞歸處理剩餘部分。
3. tmp->next = head 完成當前對交換。
4. 返回 tmp 作為新頭。

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

總結

迭代法空間 O(1)，遞歸法空間 O(n) 但代碼極簡。鏈表指針操作核心在於「先斷後連、順序不亂」，畫圖輔助理解最有效。