Java详解LeetCode 热题 100(27):LeetCode 21. 合并两个有序链表（Merge Two Sorted Lists）详解

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. 举一反三：学会将算法思想应用到其他问题

总结：
合并两个有序链表是链表操作的基础题目，也是归并思想的重要体现。掌握这道题不仅能提高链表操作能力，还能为后续学习更复杂的链表算法打下坚实基础。建议初学者从迭代法开始，逐步掌握递归法，最终能够灵活运用多种方法解决问题。