您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 程式設計入門

Java 合併兩個有序鏈表：雙指針原地合併算法圖解與實現

編輯：Java 程式設計入門

問題描述

給定兩個單調遞增的單鏈表，將它們合併為一個新的有序鏈表並返回。合併後的鏈表應包含原兩個鏈表的所有節點，並保持遞增順序。

示例：


輸入：l1 = 1 -> 3 -> 5, l2 = 2 -> 4 -> 6
輸出：1 -> 2 -> 3 -> 4 -> 5 -> 6

核心思路：虛擬頭節點 + 雙指針

使用一個 哨兵節點 (dummy head) 簡化邊界條件處理，雙指針 p1、p2 分別遍歷兩個鏈表，每次將較小值節點接入結果鏈表。

完整 Java 實現


public class MergeTwoSortedLists {

    // 鏈表節點定義
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    /**
     * 合併兩個有序鏈表 (迭代法)
     * 時間複雜度: O(m + n) - m, n 為兩鏈表長度
     * 空間複雜度: O(1) - 僅使用常數額外空間
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 1. 創建虛擬頭節點，簡化邊界處理
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;  // tail 指向結果鏈表尾部
        
        // 2. 雙指針遍歷
        ListNode p1 = l1;
        ListNode p2 = l2;
        
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                tail.next = p1;  // 接入 p1 節點
                p1 = p1.next;    // p1 前進
            } else {
                tail.next = p2;  // 接入 p2 節點
                p2 = p2.next;    // p2 前進
            }
            tail = tail.next;    // tail 前進
        }
        
        // 3. 接入剩餘部分 (只有一個鏈表可能有剩餘)
        tail.next = (p1 != null) ? p1 : p2;
        
        // 4. 返回真實頭節點
        return dummy.next;
    }

    // 測試輔助方法
    public static ListNode createList(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
    
    public static void printList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val);
            if (head.next != null) sb.append(" -> ");
            head = head.next;
        }
        System.out.println(sb);
    }

    public static void main(String[] args) {
        MergeTwoSortedLists solution = new MergeTwoSortedLists();
        
        ListNode l1 = createList(1, 3, 5, 7);
        ListNode l2 = createList(2, 4, 6, 8, 10);
        
        System.out.print("鏈表 1: "); printList(l1);
        System.out.print("鏈表 2: "); printList(l2);
        
        ListNode merged = solution.mergeTwoLists(l1, l2);
        System.out.print("合併後: "); printList(merged);
    }
}

算法過程圖解


初始狀態:
l1: 1 → 3 → 5
l2: 2 → 4 → 6

dummy(0) → null
tail = dummy
p1 = 1, p2 = 2

第 1 輪: p1.val(1) <= p2.val(2)
dummy → 1
tail = 1, p1 = 3

第 2 輪: p1.val(3) > p2.val(2)
dummy → 1 → 2
tail = 2, p2 = 4

第 3 輪: p1.val(3) <= p2.val(4)
dummy → 1 → 2 → 3
tail = 3, p1 = 5

第 4 輪: p1.val(5) > p2.val(4)
dummy → 1 → 2 → 3 → 4
tail = 4, p2 = 6

第 5 輪: p1.val(5) <= p2.val(6)
dummy → 1 → 2 → 3 → 4 → 5
tail = 5, p1 = null

循環結束，p1 為 null
tail.next = p2 (即 6)
結果: 1 → 2 → 3 → 4 → 5 → 6

遞歸版本實現 (簡潔但有棧溢出風險)


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

複雜度：時間 O(m+n)，空間 O(m+n) 遞歸棧深度。長鏈表慎用。

Java 特有技巧：無指針如何模擬指針操作

Java 無顯式指針，但 對象引用本質上就是指針：

ListNode p1 = l1; → p1 指向 l1 所指節點
p1 = p1.next; → 指針後移
tail.next = p1; → 修改 tail 節點的 next 域，改變鏈表結構
dummy 節點的 next 域最終指向合併後的真實頭節點

進階變體與擴展

1. 合併 K 個有序鏈表 (LeetCode 23)


// 分治法: 兩兩合併，時間 O(N log K)
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return merge(lists, 0, lists.length - 1);
}

private ListNode merge(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];
    int mid = left + (right - left) / 2;
    ListNode l1 = merge(lists, left, mid);
    ListNode l2 = merge(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}

2. 就地合併不創建新節點

本文算法本身就是就地合併，直接重用原節點，無額外內存分配 (除 dummy 節點)。

3. 降序鏈表合併


// 只需修改比較條件
if (p1.val >= p2.val) {  // 改為 >=
    tail.next = p1;
    p1 = p1.next;
} else {
    tail.next = p2;
    p2 = p2.next;
}

常見錯誤與調試技巧

❌ 錯誤 1：忘記處理剩餘節點


// 缺少這行會導致長鏈表尾部丟失
tail.next = (p1 != null) ? p1 : p2;

❌ 錯誤 2：死循環 (形成環)


// 錯誤：未正確前進指針
tail.next = p1;
// 缺少: p1 = p1.next; tail = tail.next;

❌ 錯誤 3：空指針異常


// 直接訪問 p1.val 而未判空
while (p1 != null && p2 != null) {  // 必須雙重判空
    if (p1.val <= p2.val) { ... }
}

調試技巧：可視化鏈表結構


// 使用 IDE 調試時，為 ListNode 添加 toString()
@Override
public String toString() {
    return val + (next != null ? " -> " + next : "");
}
// 直接在 Watch 窗口查看 head 變量，直觀看到完結構