LeetCode 24：兩兩交換鏈表中的節點 - 圖解與代碼實現

這道題目要求將單鏈表中的節點兩兩交換。例如給定 1->2->3->4，交換後變為 2->1->4->3。核心難點在於指針操作的正確性，稍有不慎就會導致鏈表斷裂或丟失節點。

核心思路：四指針協作

我們需要同時處理三個任務：交換當前兩個節點、連接前一段已處理的鏈表、保存後續待處理的鏈表。這需要四個關鍵指針配合：

• prev：指向待交換的第一個節點
• cur：指向待交換的第二個節點
• next：保存 cur->next，用於連接下一輪交換
• pprev：指向前一輪交換後的尾節點，用於連接當前交換後的頭節點

算法流程

1. 處理邊界情況：鏈表為空或只有一個節點，直接返回
2. 記錄新頭節點（原第二個節點）
3. 初始化四個指針完成第一組交換
4. 循環處理剩餘節點：每輪交換兩個節點，並通過 pprev 連接上一輪結果
5. 處理奇數長度鏈表的尾節點

完整 C++ 實現

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        
        ListNode* newHead = head->next;  // 新頭節點
        ListNode* prev = head;
        ListNode* cur = head->next;
        ListNode* next = cur->next;
        
        // 第一組交換
        cur->next = prev;
        prev->next = nullptr;
        ListNode* pprev = prev;  // 指向已處理部分的尾部
        
        while (next) {
            prev = next;
            cur = prev->next;
            if (!cur) {  // 奇數長度，最後一個節點無法配對
                pprev->next = prev;
                break;
            }
            next = cur->next;
            cur->next = prev;
            prev->next = nullptr;
            pprev->next = cur;  // 連接上一輪結果
            pprev = prev;       // 更新尾部指針
        }
        return newHead;
    }
};

關鍵點總結

• 使用 pprev 維護已處理鏈表的尾部，避免斷鏈
• 每輪交換前必須保存 next 指針，否則會丟失後續節點
• 循環結束條件需同時考慮偶數/奇數長度鏈表
• 時間複雜度 O(n)，空間複雜度 O(1)