Java 合併兩個有序鏈表：遞歸與迭代雙解法詳解

問題描述

給定兩個單調遞增的單鏈表，將它們合併為一個新的有序鏈表並返回頭節點。要求不創建新節點，直接拼接原節點，空間複雜度 O(1)。

數據結構定義

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

解法一：迭代法 (推薦，空間 O(1))

引入虛擬頭節點 dummy，雙指針 p1、p2 遍歷兩表，比較值將較小節點接在 tail 後，最後處理剩餘尾部。

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;
    }

    // 直接拼接剩餘部分
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

解法二：遞歸法 (簡潔，空間 O(m+n) 棧)

public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    if (l1.val <= l2.val) {
        l1.next = mergeTwoListsRecursive(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoListsRecursive(l1, l2.next);
        return l2;
    }
}

複雜度分析

關鍵點總結

1. 虛擬頭節點：統一處理頭節點為空的邊界情況，代碼更簡潔。
2. 尾指針：始終指向合併鏈表最後一個節點，O(1) 拼接新節點。
3. 原地修改：直接重用原節點 next 指針，無額外內存分配。
4. 邊界條件：任一表為空直接返回另一表；循環結束後直接掛載非空剩餘段。

測試用例

public static void main(String[] args) {
    // 1 -> 3 -> 5
    ListNode l1 = new ListNode(1);
    l1.next = new ListNode(3);
    l1.next.next = new ListNode(5);

    // 2 -> 4 -> 6
    ListNode l2 = new ListNode(2);
    l2.next = new ListNode(4);
    l2.next.next = new ListNode(6);

    ListNode merged = mergeTwoLists(l1, l2);
    while (merged != null) {
        System.out.print(merged.val + " "); // 1 2 3 4 5 6
        merged = merged.next;
    }
}

擴展：合併 K 個有序鏈表

若需合併 K 個表，可採用分治法 (兩兩合併) 或優先隊列 (最小堆) 維護 K 個頭節點，時間複雜度 O(N log K)，N 為總節點數。

總結

合併兩個有序鏈表是鏈表操作的基石題。迭代法以 O(1) 空間優勢成為面試與工程首選；遞歸法代碼極簡，適合快速原型。掌握虛擬頭節點 + 雙指針 + 尾部拼接模板，可輕鬆應對各類鏈表合併變體。