【忍者算法】从拉链到链表：探索有序链表的合并之道｜LeetCode 21 合并两个有序链表

从拉链到链表：探索有序链表的合并之道

生活中的合并

想象你正在整理两叠按日期排好序的收据。最自然的方式就是：拿起两叠收据，每次比较最上面的日期，选择日期较早的那张放入新的一叠中。这个简单的日常操作，恰恰就是我们今天要讨论的有序链表合并问题的真实写照。
问题描述

LeetCode第21题"合并两个有序链表"要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
例如：

1. 输入：1 → 2 → 4, 1 → 3 → 4
2. 输出：1 → 1 → 2 → 3 → 4 → 4
4. 输入：空链表, 0
5. 输出：0
7. 输入：空链表, 空链表
8. 输出：空链表

复制代码

暴力解法：转换为数组排序

最直观的想法可能是：把两个链表的值都放到一个数组里，排序后再创建新链表。这种方法虽然不够优雅，但对于理解问题很有帮助。
暴力解法实现

1. public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
2.     // 创建数组存储所有节点值
3.     List<Integer> values = new ArrayList<>();
4.    
5.     // 遍历第一个链表
6.     while (list1 != null) {
7.         values.add(list1.val);
8.         list1 = list1.next;
9.     }
10.    
11.     // 遍历第二个链表
12.     while (list2 != null) {
13.         values.add(list2.val);
14.         list2 = list2.next;
15.     }
16.    
17.     // 排序数组
18.     Collections.sort(values);
19.    
20.     // 构建新链表
21.     ListNode dummy = new ListNode(0);  // 哨兵节点
22.     ListNode current = dummy;
23.    
24.     // 根据排序后的数组创建新链表
25.     for (int value : values) {
26.         current.next = new ListNode(value);
27.         current = current.next;
28.     }
29.    
30.     return dummy.next;
31. }

复制代码

优化解法：双指针遍历

既然输入的链表已经排好序，我们完全可以模拟整理收据的过程：同时遍历两个链表，每次选择较小的节点连接到结果链表中。这就像拉链一样，将两个有序序列合并成一个。
代码实现与详解

[code]public ListNode mergeTwoLists(ListNode list1, ListNode list2) {    // 创建哨兵节点，简化边界情况处理    ListNode dummy = new ListNode(0);    ListNode current = dummy;        // 当两个链表都不为空时，比较并连接    while (list1 != null && list2 != null) {        if (list1.val