LeetCode 24. 兩兩交換鏈表節點：遞歸與迭代雙解法圖解

LeetCode 24. 兩兩交換鏈表節點：遞歸與迭代雙解法圖解

題目： 給定一個鏈表，兩兩交換相鄰節點，並返回交換後的頭節點。不能修改節點值，只能交換節點本身。空間複雜度 O(1)。

示例： 1→2→3→4 → 2→1→4→3

一、 遞歸解法：簡潔優雅，利用調用棧回溯重鏈

核心邏輯

1. 終止條件： 節點為空 或 僅剩單節點 (head == null || head.next == null)，直接返回。
2. 遞歸處理： 假設 head 和 head.next 為待交換的第一對 (first, second)。
   遞歸調用 swapPairs(head.next.next) 處理剩餘鏈表，返回新的子鏈表頭 restHead。
3. 交換當前對：
   • first.next = restHead (第一個節點指向後續已交換好的鏈表)
   • second.next = first (第二個節點指向第一個，完成交換)
4. 返回新頭： second (即原 head.next)。

代碼實現

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 終止條件
        if (head == null || head.next == null) {
            return head;
        }
        // 當前待交換的兩個節點
        ListNode first = head;
        ListNode second = head.next;
        
        // 遞歸處理剩餘節點
        ListNode restHead = swapPairs(second.next);
        
        // 交換當前對
        first.next = restHead;
        second.next = first;
        
        // 返回新頭節點
        return second;
    }
}

複雜度分析

• 時間： O(n) — 每個節點訪問常數次。
• 空間： O(n) — 遞歸調用棧深度 n/2 (非 O(1)，但代碼極簡)。

二、 迭代解法：真正 O(1) 空間，指針操作核心

核心思路：虛擬頭節點 + 三指針協作

引入 dummy 虛擬頭節點簡化邊界處理 (頭節點可能改變)。維護三個指針：

• prev：指向**已處理部分的尾節點** (初始指向 dummy)。
• first：待交換的第一個節點 (prev.next)。
• second：待交換的第二個節點 (first.next)。

交換步驟 (圖解關鍵)

prev → first → second → nextPair
           ↓        ↓
        (斷開)   (斷開)

重鏈：
prev.next = second
second.next = first
first.next = nextPair

指針前移：
prev = first
first = nextPair
second = first?.next

代碼實現

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = first.next;
            ListNode nextPair = second.next; // 保存下一組頭
            
            // 交換
            prev.next = second;
            second.next = first;
            first.next = nextPair;
            
            // 前移準備下一輪
            prev = first;
        }
        
        return dummy.next;
    }
}

複雜度分析

• 時間： O(n) — 單次遍歷。
• 空間： O(1) — 僅使用常數額外指針，滿足題目要求。

三、 關鍵細節與避坑指南

1. 虛擬頭節點 (dummy) 是神器： 統一了頭節點交換與中間節點交換的邏輯，無需單獨處理 head 變更。
2. 保存 nextPair 必須在斷開指針前： second.next 修改後原鏈接丟失，必須先存 ListNode nextPair = second.next;。
3. prev 前移到 first (而非 second)： 交換後 first 成為該對的尾節點，下一輪的 prev 應指向它。
4. 循環條件： prev.next != null && prev.next.next != null 確保至少有兩個節點可交換。
5. 不可修改節點值： 題目強制要求交換節點對象，而非交換 val 字段。

四、 總結對比

掌握「虛擬頭節點 + 三指針」迭代模板，不僅能解決此題，更是處理「鏈表局部反轉」「K 個一組翻轉 (LeetCode 25)」「刪除倒數第 N 個節點」等經典鏈表題的通用利器。