1. 題目描述

將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例 1:

輸入：list1 = [1,2,4], list2 = [1,3,4]
輸出：[1,1,2,3,4,4]

示例 2:

輸入：list1 = [], list2 = []
輸出：[]

示例 3:

輸入：list1 = [], list2 = [0]
輸出：[0]

提示：

• 兩個鏈表的節點數目范圍是 [0, 50]
• -100 <= Node.val <= 100
• list1 和 list2 均按 非遞減順序 排列

1.1 鏈表節點定義

/*** 單鏈表節點的定義*/
public class ListNode {int val;           // 節點的值ListNode next;     // 指向下一個節點的指針// 無參構造函數ListNode() {}// 帶值的構造函數ListNode(int val) { this.val = val; }// 帶值和下一個節點的構造函數ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

2. 理解題目

合并兩個有序鏈表是鏈表操作中的經典問題，類似于歸并排序中的合并操作。

關鍵概念：

1. 有序性：兩個輸入鏈表都是按非遞減順序排列
2. 拼接操作：不是創建新的節點，而是重新組織現有節點
3. 保持有序：合并后的鏈表必須保持有序性

2.1 問題可視化

示例 1 可視化： list1 = [1,2,4], list2 = [1,3,4]

原始鏈表：
list1: 1 → 2 → 4 → null
list2: 1 → 3 → 4 → null合并過程：
步驟1: 比較 1 和 1，選擇第一個 1
步驟2: 比較 2 和 1，選擇 1
步驟3: 比較 2 和 3，選擇 2
步驟4: 比較 4 和 3，選擇 3
步驟5: 比較 4 和 4，選擇第一個 4
步驟6: 剩余的 4 直接連接結果鏈表：
result: 1 → 1 → 2 → 3 → 4 → 4 → null

2.2 核心挑戰

1. 雙指針管理：需要同時跟蹤兩個鏈表的當前位置
2. 邊界條件：處理其中一個鏈表為空的情況
3. 節點連接：正確連接選中的節點到結果鏈表
4. 剩余節點處理：當一個鏈表遍歷完后，處理另一個鏈表的剩余節點

3. 解法一：迭代法（哨兵節點）

3.1 算法思路

使用哨兵節點簡化邊界條件處理，通過雙指針比較兩個鏈表的當前節點值。

核心步驟：

1. 創建哨兵節點作為結果鏈表的頭部
2. 使用雙指針分別遍歷兩個鏈表
3. 比較當前節點值，選擇較小的節點連接到結果鏈表
4. 移動對應的指針到下一個節點
5. 當一個鏈表遍歷完后，直接連接另一個鏈表的剩余部分

3.2 Java代碼實現

/*** 解法一：迭代法（哨兵節點）* 時間復雜度：O(m + n)，其中 m 和 n 分別是兩個鏈表的長度* 空間復雜度：O(1)，只使用常數額外空間*/
class Solution1 {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 創建哨兵節點，簡化邊界條件處理ListNode sentinel = new ListNode(-1);ListNode current = sentinel;// 同時遍歷兩個鏈表while (list1 != null && list2 != null) {// 比較當前節點的值，選擇較小的節點if (list1.val <= list2.val) {current.next = list1;  // 連接較小的節點list1 = list1.next;    // 移動指針} else {current.next = list2;  // 連接較小的節點list2 = list2.next;    // 移動指針}current = current.next;    // 移動結果鏈表指針}// 連接剩余的節點（其中一個鏈表已經遍歷完）current.next = (list1 != null) ? list1 : list2;// 返回真正的頭節點（跳過哨兵節點）return sentinel.next;}
}

3.3 詳細執行過程演示

/*** 帶詳細調試輸出的迭代法實現*/
public class IterativeMethodDemo {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {System.out.println("=== 迭代法合并兩個有序鏈表 ===");System.out.println("list1: " + printList(list1));System.out.println("list2: " + printList(list2));System.out.println();ListNode sentinel = new ListNode(-1);ListNode current = sentinel;int step = 1;System.out.println("開始合并過程：");while (list1 != null && list2 != null) {System.out.println("步驟 " + step + ":");System.out.println("  list1 當前節點: " + list1.val);System.out.println("  list2 當前節點: " + list2.val);if (list1.val <= list2.val) {System.out.println("  選擇 list1 的節點: " + list1.val);current.next = list1;list1 = list1.next;} else {System.out.println("  選擇 list2 的節點: " + list2.val);current.next = list2;list2 = list2.next;}current = current.next;System.out.println("  當前結果鏈表: " + printList(sentinel.next));System.out.println();step++;}// 處理剩余節點if (list1 != null) {System.out.println("list1 有剩余節點，直接連接: " + printList(list1));current.next = list1;} else if (list2 != null) {System.out.println("list2 有剩余節點，直接連接: " + printList(list2));current.next = list2;} else {System.out.println("兩個鏈表都已遍歷完成");}System.out.println("最終結果: " + printList(sentinel.next));return sentinel.next;}// 輔助方法：打印鏈表private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");ListNode current = head;while (current != null) {sb.append(current.val);if (current.next != null) {sb.append(" -> ");}current = current.next;}sb.append("]");return sb.toString();}
}

3.4 執行結果示例

示例 1：list1 = [1,2,4], list2 = [1,3,4]

=== 迭代法合并兩個有序鏈表 ===
list1: [1 -> 2 -> 4]
list2: [1 -> 3 -> 4]開始合并過程：
步驟 1:list1 當前節點: 1list2 當前節點: 1選擇 list1 的節點: 1當前結果鏈表: [1]步驟 2:list1 當前節點: 2list2 當前節點: 1選擇 list2 的節點: 1當前結果鏈表: [1 -> 1]步驟 3:list1 當前節點: 2list2 當前節點: 3選擇 list1 的節點: 2當前結果鏈表: [1 -> 1 -> 2]步驟 4:list1 當前節點: 4list2 當前節點: 3選擇 list2 的節點: 3當前結果鏈表: [1 -> 1 -> 2 -> 3]步驟 5:list1 當前節點: 4list2 當前節點: 4選擇 list1 的節點: 4當前結果鏈表: [1 -> 1 -> 2 -> 3 -> 4]list2 有剩余節點，直接連接: [4]
最終結果: [1 -> 1 -> 2 -> 3 -> 4 -> 4]

3.5 復雜度分析

時間復雜度： O(m + n)

• m 和 n 分別是兩個鏈表的長度
• 每個節點最多被訪問一次
• 總的比較次數不超過 m + n - 1 次

空間復雜度： O(1)

• 只使用了幾個指針變量
• 不需要額外的數據結構存儲

3.6 優缺點分析

優點：

1. 空間效率高：O(1) 空間復雜度
2. 思路清晰：邏輯直觀，易于理解
3. 穩定性好：相等元素的相對順序保持不變
4. 邊界處理簡單：哨兵節點簡化了代碼

缺點：

1. 需要額外節點：創建了一個哨兵節點
2. 指針操作較多：需要仔細處理多個指針的移動

4. 解法二：遞歸法

4.1 算法思路

遞歸法利用了問題的自相似性：合并兩個鏈表的問題可以分解為選擇較小的頭節點，然后遞歸合并剩余部分。

遞歸關系：

• 如果 list1 為空，返回 list2
• 如果 list2 為空，返回 list1
• 如果 list1.val <= list2.val，則 list1.next = mergeTwoLists(list1.next, list2)，返回 list1
• 否則，list2.next = mergeTwoLists(list1, list2.next)，返回 list2

4.2 Java代碼實現

/*** 解法二：遞歸法* 時間復雜度：O(m + n)* 空間復雜度：O(m + n)，遞歸調用棧的深度*/
class Solution2 {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 遞歸終止條件if (list1 == null) {return list2;}if (list2 == null) {return list1;}// 遞歸主體：選擇較小的節點，遞歸處理剩余部分if (list1.val <= list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}}
}

4.3 遞歸過程可視化

/*** 帶調試輸出的遞歸法實現*/
public class RecursiveMethodDemo {private int depth = 0; // 遞歸深度計數器public ListNode mergeTwoLists(ListNode list1, ListNode list2) {depth++;String indent = getIndent(depth);System.out.println(indent + "遞歸調用 depth=" + depth);System.out.println(indent + "list1: " + printList(list1));System.out.println(indent + "list2: " + printList(list2));// 遞歸終止條件if (list1 == null) {System.out.println(indent + "list1為空，返回list2: " + printList(list2));depth--;return list2;}if (list2 == null) {System.out.println(indent + "list2為空，返回list1: " + printList(list1));depth--;return list1;}ListNode result;if (list1.val <= list2.val) {System.out.println(indent + "選擇list1的節點: " + list1.val);System.out.println(indent + "遞歸處理: mergeTwoLists(" + printList(list1.next) + ", " + printList(list2) + ")");list1.next = mergeTwoLists(list1.next, list2);result = list1;System.out.println(indent + "遞歸返回，list1.next已設置");} else {System.out.println(indent + "選擇list2的節點: " + list2.val);System.out.println(indent + "遞歸處理: mergeTwoLists(" + printList(list1) + ", " + printList(list2.next) + ")");list2.next = mergeTwoLists(list1, list2.next);result = list2;System.out.println(indent + "遞歸返回，list2.next已設置");}System.out.println(indent + "返回結果: " + printList(result));depth--;return result;}private String getIndent(int depth) {StringBuilder sb = new StringBuilder();for (int i = 0; i < depth; i++) {sb.append("  ");}return sb.toString();}private String printList(ListNode head) {if (head == null) return "null";StringBuilder sb = new StringBuilder();sb.append("[");ListNode current = head;int count = 0;while (current != null && count < 3) { // 限制輸出長度sb.append(current.val);if (current.next != null && count < 2) {sb.append(",");}current = current.next;count++;}if (current != null) {sb.append("...");}sb.append("]");return sb.toString();}
}

4.4 遞歸執行示例

示例：list1 = [1,2], list2 = [1,3]

  遞歸調用 depth=1list1: [1,2]list2: [1,3]選擇list1的節點: 1遞歸處理: mergeTwoLists([2], [1,3])遞歸調用 depth=2list1: [2]list2: [1,3]選擇list2的節點: 1遞歸處理: mergeTwoLists([2], [3])遞歸調用 depth=3list1: [2]list2: [3]選擇list1的節點: 2遞歸處理: mergeTwoLists(null, [3])遞歸調用 depth=4list1: nulllist2: [3]list1為空，返回list2: [3]遞歸返回，list1.next已設置返回結果: [2,3]遞歸返回，list2.next已設置返回結果: [1,2,3]遞歸返回，list1.next已設置返回結果: [1,1,2,3]

4.5 復雜度分析

時間復雜度： O(m + n)

• 遞歸調用的總次數等于兩個鏈表的節點數之和
• 每次遞歸調用的時間復雜度為 O(1)

空間復雜度： O(m + n)

• 遞歸調用棧的最大深度為 m + n
• 每層遞歸使用常數空間

4.6 優缺點分析

優點：

1. 代碼簡潔：遞歸實現非常簡潔優雅
2. 邏輯清晰：遞歸思維直觀，易于理解
3. 無需哨兵節點：直接返回合并后的頭節點

缺點：

1. 空間開銷大：O(m + n) 的遞歸棧空間
2. 可能棧溢出：對于很長的鏈表可能導致棧溢出
3. 性能稍差：函數調用開銷比迭代法大

5. 解法三：原地合并法

5.1 算法思路

不使用哨兵節點，直接確定合并后的頭節點，然后進行原地合并。

/*** 解法三：原地合并法* 時間復雜度：O(m + n)* 空間復雜度：O(1)*/
class Solution3 {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 處理空鏈表的情況if (list1 == null) return list2;if (list2 == null) return list1;// 確定合并后的頭節點ListNode head, current;if (list1.val <= list2.val) {head = current = list1;list1 = list1.next;} else {head = current = list2;list2 = list2.next;}// 合并剩余節點while (list1 != null && list2 != null) {if (list1.val <= list2.val) {current.next = list1;list1 = list1.next;} else {current.next = list2;list2 = list2.next;}current = current.next;}// 連接剩余節點current.next = (list1 != null) ? list1 : list2;return head;}
}

5.2 優缺點分析

優點：

1. 真正的O(1)空間：不創建任何額外節點
2. 性能較好：避免了創建哨兵節點的開銷

缺點：

1. 代碼復雜：需要單獨處理頭節點的確定
2. 邏輯繁瑣：邊界條件處理相對復雜

6. 解法四：優化遞歸法

6.1 算法思路

通過調整參數順序，簡化遞歸邏輯，使代碼更加簡潔。

/*** 解法四：優化遞歸法* 時間復雜度：O(m + n)* 空間復雜度：O(m + n)*/
class Solution4 {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 確保list1指向值較小的鏈表if (list1 == null || (list2 != null && list1.val > list2.val)) {ListNode temp = list1;list1 = list2;list2 = temp;}// 遞歸處理if (list1 != null) {list1.next = mergeTwoLists(list1.next, list2);}return list1;}
}

7. 完整測試用例

7.1 測試框架

import java.util.*;/*** 合并兩個有序鏈表完整測試類*/
public class MergeTwoSortedListsTest {/*** 創建測試鏈表的輔助方法*/public static ListNode createList(int[] values) {if (values.length == 0) {return null;}ListNode head = new ListNode(values[0]);ListNode current = head;for (int i = 1; i < values.length; i++) {current.next = new ListNode(values[i]);current = current.next;}return head;}/*** 將鏈表轉換為數組，便于比較結果*/public static int[] listToArray(ListNode head) {List<Integer> result = new ArrayList<>();ListNode current = head;while (current != null) {result.add(current.val);current = current.next;}return result.stream().mapToInt(i -> i).toArray();}/*** 運行所有測試用例*/public static void runAllTests() {System.out.println("=== 合并兩個有序鏈表完整測試 ===\n");// 測試用例TestCase[] testCases = {new TestCase(new int[]{1, 2, 4}, new int[]{1, 3, 4}, new int[]{1, 1, 2, 3, 4, 4}, "示例1：常規合并"),new TestCase(new int[]{}, new int[]{}, new int[]{}, "示例2：兩個空鏈表"),new TestCase(new int[]{}, new int[]{0}, new int[]{0}, "示例3：一個空鏈表"),new TestCase(new int[]{1, 2, 3}, new int[]{4, 5, 6}, new int[]{1, 2, 3, 4, 5, 6}, "所有list1元素都小于list2"),new TestCase(new int[]{4, 5, 6}, new int[]{1, 2, 3}, new int[]{1, 2, 3, 4, 5, 6}, "所有list2元素都小于list1"),new TestCase(new int[]{1, 3, 5}, new int[]{2, 4, 6}, new int[]{1, 2, 3, 4, 5, 6}, "交替合并"),new TestCase(new int[]{1}, new int[]{2}, new int[]{1, 2}, "單節點鏈表"),new TestCase(new int[]{1, 1, 1}, new int[]{2, 2, 2}, new int[]{1, 1, 1, 2, 2, 2}, "重復元素"),new TestCase(new int[]{-3, -1, 4}, new int[]{-2, 0, 5}, new int[]{-3, -2, -1, 0, 4, 5}, "包含負數"),new TestCase(new int[]{1, 2, 3, 7, 8}, new int[]{4, 5, 6}, new int[]{1, 2, 3, 4, 5, 6, 7, 8}, "長度不等的鏈表")};Solution1 solution1 = new Solution1();Solution2 solution2 = new Solution2();Solution3 solution3 = new Solution3();for (int i = 0; i < testCases.length; i++) {TestCase testCase = testCases[i];System.out.println("測試用例 " + (i + 1) + ": " + testCase.description);System.out.println("list1: " + Arrays.toString(testCase.list1));System.out.println("list2: " + Arrays.toString(testCase.list2));System.out.println("期望結果: " + Arrays.toString(testCase.expected));// 創建測試鏈表（每種方法需要獨立的鏈表）ListNode head1_1 = createList(testCase.list1);ListNode head2_1 = createList(testCase.list2);ListNode head1_2 = createList(testCase.list1);ListNode head2_2 = createList(testCase.list2);ListNode head1_3 = createList(testCase.list1);ListNode head2_3 = createList(testCase.list2);// 測試迭代法ListNode result1 = solution1.mergeTwoLists(head1_1, head2_1);int[] array1 = listToArray(result1);// 測試遞歸法ListNode result2 = solution2.mergeTwoLists(head1_2, head2_2);int[] array2 = listToArray(result2);// 測試原地合并法ListNode result3 = solution3.mergeTwoLists(head1_3, head2_3);int[] array3 = listToArray(result3);System.out.println("迭代法結果: " + Arrays.toString(array1));System.out.println("遞歸法結果: " + Arrays.toString(array2));System.out.println("原地合并法結果: " + Arrays.toString(array3));boolean passed = Arrays.equals(array1, testCase.expected) &&Arrays.equals(array2, testCase.expected) &&Arrays.equals(array3, testCase.expected);System.out.println("測試結果: " + (passed ? "? 通過" : "? 失敗"));System.out.println();}}/*** 測試用例類*/static class TestCase {int[] list1;int[] list2;int[] expected;String description;TestCase(int[] list1, int[] list2, int[] expected, String description) {this.list1 = list1;this.list2 = list2;this.expected = expected;this.description = description;}}public static void main(String[] args) {runAllTests();}
}

7.2 性能測試

/*** 性能測試類*/
public class PerformanceTest {public static void performanceComparison() {System.out.println("=== 性能對比測試 ===\n");int[] sizes = {100, 1000, 5000};Solution1 iterativeSolution = new Solution1();Solution2 recursiveSolution = new Solution2();Solution3 inPlaceSolution = new Solution3();for (int size : sizes) {System.out.println("測試規模: " + size + " 個節點");// 創建大型測試鏈表int[] values1 = new int[size / 2];int[] values2 = new int[size - size / 2];// 生成有序數據for (int i = 0; i < values1.length; i++) {values1[i] = i * 2; // 偶數}for (int i = 0; i < values2.length; i++) {values2[i] = i * 2 + 1; // 奇數}// 測試迭代法ListNode head1_1 = MergeTwoSortedListsTest.createList(values1);ListNode head2_1 = MergeTwoSortedListsTest.createList(values2);long startTime1 = System.nanoTime();ListNode result1 = iterativeSolution.mergeTwoLists(head1_1, head2_1);long endTime1 = System.nanoTime();long time1 = endTime1 - startTime1;// 測試遞歸法（對于大數據可能棧溢出，需要小心）long time2 = 0;if (size <= 1000) { // 限制遞歸測試的數據規模ListNode head1_2 = MergeTwoSortedListsTest.createList(values1);ListNode head2_2 = MergeTwoSortedListsTest.createList(values2);long startTime2 = System.nanoTime();ListNode result2 = recursiveSolution.mergeTwoLists(head1_2, head2_2);long endTime2 = System.nanoTime();time2 = endTime2 - startTime2;}// 測試原地合并法ListNode head1_3 = MergeTwoSortedListsTest.createList(values1);ListNode head2_3 = MergeTwoSortedListsTest.createList(values2);long startTime3 = System.nanoTime();ListNode result3 = inPlaceSolution.mergeTwoLists(head1_3, head2_3);long endTime3 = System.nanoTime();long time3 = endTime3 - startTime3;System.out.println("迭代法耗時: " + time1 / 1000000.0 + " ms");if (time2 > 0) {System.out.println("遞歸法耗時: " + time2 / 1000000.0 + " ms");System.out.println("遞歸法相對迭代法: " + String.format("%.2f", (double) time2 / time1) + " 倍");} else {System.out.println("遞歸法: 跳過測試（避免棧溢出）");}System.out.println("原地合并法耗時: " + time3 / 1000000.0 + " ms");System.out.println("原地合并法相對迭代法: " + String.format("%.2f", (double) time3 / time1) + " 倍");System.out.println();}}public static void main(String[] args) {performanceComparison();}
}

8. 算法復雜度對比

8.1 詳細對比表格

解法	時間復雜度	空間復雜度	優點	缺點	推薦度
迭代法（哨兵節點）	O(m + n)	O(1)	空間效率高，邏輯清晰	需要額外哨兵節點	?????
遞歸法	O(m + n)	O(m + n)	代碼簡潔，思路清晰	空間開銷大，可能棧溢出	????
原地合并法	O(m + n)	O(1)	真正O(1)空間	代碼復雜，邊界處理繁瑣	???
優化遞歸法	O(m + n)	O(m + n)	代碼極簡	理解難度大，空間開銷大	??

8.2 實際性能測試結果

=== 性能對比測試 ===測試規模: 100 個節點
迭代法耗時: 0.028 ms
遞歸法耗時: 0.042 ms
遞歸法相對迭代法: 1.50 倍
原地合并法耗時: 0.025 ms
原地合并法相對迭代法: 0.89 倍測試規模: 1000 個節點
迭代法耗時: 0.156 ms
遞歸法耗時: 0.298 ms
遞歸法相對迭代法: 1.91 倍
原地合并法耗時: 0.134 ms
原地合并法相對迭代法: 0.86 倍測試規模: 5000 個節點
迭代法耗時: 0.743 ms
遞歸法: 跳過測試（避免棧溢出）
原地合并法耗時: 0.625 ms
原地合并法相對迭代法: 0.84 倍

結論：

1. 迭代法是最平衡的選擇，既有良好的性能又有清晰的邏輯
2. 原地合并法性能最好，但代碼復雜度較高
3. 遞歸法代碼最簡潔，但有棧溢出風險

9. 常見錯誤與調試技巧

9.1 常見錯誤

1. 忘記移動指針

// 錯誤寫法：忘記移動指針，導致無限循環
while (list1 != null && list2 != null) {if (list1.val <= list2.val) {current.next = list1;// 忘記移動 list1 指針} else {current.next = list2;// 忘記移動 list2 指針}current = current.next;
}// 正確寫法：記得移動指針
while (list1 != null && list2 != null) {if (list1.val <= list2.val) {current.next = list1;list1 = list1.next; // 移動指針} else {current.next = list2;list2 = list2.next; // 移動指針}current = current.next;
}

2. 忘記處理剩余節點

// 錯誤寫法：沒有處理剩余節點
while (list1 != null && list2 != null) {// 合并邏輯
}
// 缺少處理剩余節點的代碼// 正確寫法：處理剩余節點
while (list1 != null && list2 != null) {// 合并邏輯
}
current.next = (list1 != null) ? list1 : list2;

3. 遞歸終止條件錯誤

// 錯誤寫法：遞歸終止條件不完整
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}// 忘記檢查 list2 是否為 nullif (list1.val <= list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}
}// 正確寫法：完整的終止條件
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) return list2;if (list2 == null) return list1; // 不能忘記這個條件// 遞歸邏輯
}

9.2 調試技巧

1. 添加鏈表打印功能

public void debugMerge(ListNode list1, ListNode list2) {System.out.println("開始合并:");System.out.println("list1: " + listToString(list1));System.out.println("list2: " + listToString(list2));ListNode result = mergeTwoLists(list1, list2);System.out.println("結果: " + listToString(result));
}private String listToString(ListNode head) {if (head == null) return "null";StringBuilder sb = new StringBuilder();ListNode current = head;while (current != null) {sb.append(current.val);if (current.next != null) {sb.append(" -> ");}current = current.next;}return sb.toString();
}

2. 步驟跟蹤

public ListNode mergeTwoListsWithDebug(ListNode list1, ListNode list2) {ListNode sentinel = new ListNode(-1);ListNode current = sentinel;int step = 1;while (list1 != null && list2 != null) {System.out.println("步驟 " + step + ":");System.out.println("  比較 " + list1.val + " 和 " + list2.val);if (list1.val <= list2.val) {System.out.println("  選擇 " + list1.val);current.next = list1;list1 = list1.next;} else {System.out.println("  選擇 " + list2.val);current.next = list2;list2 = list2.next;}current = current.next;System.out.println("  當前結果: " + listToString(sentinel.next));step++;}current.next = (list1 != null) ? list1 : list2;return sentinel.next;
}

3. 邊界條件驗證

public void testBoundaryConditions() {System.out.println("=== 邊界條件測試 ===");// 測試空鏈表assertResult(mergeTwoLists(null, null), null, "兩個空鏈表");assertResult(mergeTwoLists(createList(new int[]{1}), null), createList(new int[]{1}), "第二個鏈表為空");assertResult(mergeTwoLists(null, createList(new int[]{1})), createList(new int[]{1}), "第一個鏈表為空");// 測試單節點assertResult(mergeTwoLists(createList(new int[]{1}), createList(new int[]{2})), createList(new int[]{1, 2}), "兩個單節點鏈表");System.out.println("邊界條件測試完成");
}private void assertResult(ListNode actual, ListNode expected, String testName) {boolean passed = isEqual(actual, expected);System.out.println(testName + ": " + (passed ? "?" : "?"));
}private boolean isEqual(ListNode list1, ListNode list2) {while (list1 != null && list2 != null) {if (list1.val != list2.val) {return false;}list1 = list1.next;list2 = list2.next;}return list1 == null && list2 == null;
}

10. 相關題目與拓展

10.1 LeetCode 相關題目

1. 23. 合并K個升序鏈表：本題的進階版本
2. 88. 合并兩個有序數組：類似思想，但操作對象是數組
3. 148. 排序鏈表：鏈表排序，可以用到合并操作
4. 1669. 合并兩個鏈表：指定位置的鏈表合并

10.2 算法思想的其他應用

1. 歸并排序

/*** 歸并排序中的合并函數*/
public void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];for (i = left; i <= right; i++) {arr[i] = temp[i - left];}
}

2. 外部排序

/*** 外部排序中合并多個已排序文件*/
public class ExternalMergeSort {public void mergeFiles(List<String> sortedFiles, String outputFile) {// 使用優先隊列（最小堆）合并多個有序文件PriorityQueue<FileReader> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.getCurrentValue(), b.getCurrentValue()));// 初始化文件讀取器for (String file : sortedFiles) {FileReader reader = new FileReader(file);if (reader.hasNext()) {pq.offer(reader);}}FileWriter writer = new FileWriter(outputFile);// 合并過程while (!pq.isEmpty()) {FileReader reader = pq.poll();writer.write(reader.getCurrentValue());if (reader.moveToNext()) {pq.offer(reader);}}writer.close();}
}

10.3 實際應用場景

1. 數據庫查詢優化：合并多個有序索引的結果
2. 分布式系統：合并來自多個節點的有序數據
3. 搜索引擎：合并多個有序的搜索結果列表
4. 時間序列數據：合并多個傳感器的有序時間序列數據

11. 學習建議與總結

11.1 學習步驟建議

第一步：理解基礎概念

1. 掌握鏈表的基本操作
2. 理解什么是有序鏈表
3. 學會鏈表的遍歷和節點連接

第二步：掌握迭代法

1. 理解哨兵節點的作用
2. 掌握雙指針的使用技巧
3. 練習處理邊界條件

第三步：學習遞歸法

1. 理解遞歸的思維方式
2. 掌握遞歸終止條件的設置
3. 理解遞歸與迭代的區別

第四步：代碼優化

1. 學習不同實現方式的優缺點
2. 掌握性能優化技巧
3. 練習代碼調試方法

第五步：拓展應用

1. 學習相關算法問題
2. 理解算法在實際中的應用
3. 練習變形題目

11.2 面試要點

常見面試問題：

1. “請實現合并兩個有序鏈表，并分析時間空間復雜度”
2. “遞歸和迭代兩種方法有什么區別？”
3. “如果要合并K個有序鏈表，你會怎么做？”
4. “能否在O(1)空間復雜度下完成合并？”
5. “如何保證算法的穩定性？”

回答要點：

1. 多種解法：能夠提供迭代和遞歸兩種解法
2. 復雜度分析：準確分析時間和空間復雜度
3. 邊界處理：考慮空鏈表等邊界情況
4. 代碼質量：代碼簡潔、邏輯清晰
5. 拓展思考：能夠聯想到相關問題和應用

11.3 最終建議

1. 多練習：通過大量練習鞏固鏈表操作技能
2. 畫圖輔助：畫圖理解鏈表合并過程
3. 代碼調試：學會添加調試信息，驗證算法正確性
4. 性能測試：比較不同方法的性能差異
5. 舉一反三：學會將算法思想應用到其他問題

總結：
合并兩個有序鏈表是鏈表操作的基礎題目，也是歸并思想的重要體現。掌握這道題不僅能提高鏈表操作能力，還能為后續學習更復雜的鏈表算法打下堅實基礎。建議初學者從迭代法開始，逐步掌握遞歸法，最終能夠靈活運用多種方法解決問題。