LeetCode 21. 合併兩個有序鏈表：迭代與遞歸雙解法圖解

LeetCode 21. 合併兩個有序鏈表：迭代與遞歸雙解法圖解

題目： 將兩個升序鏈表合併為一個新的升序鏈表並返回。新鏈表由原節點拼接而成 (不創建新節點)。

示例： l1: 1→2→4, l2: 1→3→4 → 1→1→2→3→4→4

一、 迭代解法：虛擬頭節點 + 雙指針原地拼接 (推薦)

核心思路

1. 創建 dummy 虛擬頭節點，tail 指針追蹤合併鏈表尾部。
2. 同時遍歷 l1 和 l2，比較節點值，將較小節點接在 tail 後，推進對應指針與 tail。
3. 任一鏈表耗盡後，將另一鏈表剩餘部分直接接在 tail 後 (已有序，無需逐個比較)。
4. 返回 dummy.next。

代碼實現

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next; // 尾指針前移
        }
        
        // 連接剩餘部分 (二者必有一為 null)
        tail.next = (l1 != null) ? l1 : l2;
        
        return dummy.next;
    }
}

圖解關鍵步驟

初始: dummy → null
       tail
l1: 1 → 3 → 5
l2: 2 → 4 → 6

比較 1 vs 2 → 接 1
dummy → 1
       tail
l1:     3 → 5
l2: 2 → 4 → 6

比較 3 vs 2 → 接 2
dummy → 1 → 2
             tail
l1:     3 → 5
l2:       4 → 6
... 以此類推

複雜度分析

• 時間： O(m + n) — 每個節點恰好訪問/鏈接一次。
• 空間： O(1) — 僅使用常數額外指針 (dummy, tail)，符合原地合併要求。

二、 遞歸解法：聲明式優雅，利用調用棧隱式尾指針

核心邏輯

1. 終止條件： 任一鏈表為空，直接返回另一鏈表。
2. 遞歸選擇： 比較 l1.val 和 l2.val，值較小的節點作為**當前合併結果的頭節點**。
3. 遞歸調用： 該節點的 next 指向 剩餘部分的合併結果 (即遞歸調用)。
4. 返回： 選定的頭節點。

代碼實現

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

複雜度分析

• 時間： O(m + n) — 同迭代。
• 空間： O(m + n) — 遞歸調用棧深度等於合併後鏈表長度，**不滿足 O(1) 空間要求**，極長鏈表可能棧溢出。

三、 關鍵細節與避坑指南

1. 虛擬頭節點消除邊界判斷： 無需單獨處理「合併鏈表為空」的情況，tail 始終指向當前尾節點。
2. 尾指針前移時機： 必須在 tail.next = ... **之後** 執行 tail = tail.next，否則丟失鏈接。
3. 剩餘部分直接連接： 利用「已有序」特性，tail.next = l1 != null ? l1 : l2 一步到位，避免多餘循環。
4. 穩定性： 使用 <= 而非 <，保證相等值時 l1 節點在前，維持相對順序 (穩定合併)。
5. 不創建新節點： 僅重排 next 指針，原節點對象不變，滿足題目「拼接原節點」要求。

四、 總結對比與選型建議

五、 進階變體：合併 K 個有序鏈表 (LeetCode 23)

本題是合併 K 表的基礎子問題。K 表合併優化方案：

• 分治法： 兩兩合併，時間 O(N log K)，空間 O(log K) (遞歸棧) 或 O(1) (迭代)。
• 優先隊列 (最小堆)： 維護 K 個頭節點最小堆，每次取最小接入結果，時間 O(N log K)，空間 O(K)。

掌握「虛擬頭節點 + 雙指針」迭代模板，不僅能高效解決合併兩有序鏈表，更是「合併 K 表」「歸併排序鏈表」「刪除鏈表倒數第 N 個節點」等經典題目的核心構建塊。