【忍者算法】从拉链到链表：探索有序链表的合并之道｜LeetCode 21 合并两个有序链表
从拉链到链表：探索有序链表的合并之道生活中的合并
想象你正在整理两叠按日期排好序的收据。最自然的方式就是：拿起两叠收据，每次比较最上面的日期，选择日期较早的那张放入新的一叠中。这个简单的日常操作，恰恰就是我们今天要讨论的有序链表合并问题的真实写照。
问题描述
LeetCode第21题"合并两个有序链表"要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
例如：
输入：1 → 2 → 4, 1 → 3 → 4
输出：1 → 1 → 2 → 3 → 4 → 4
输入：空链表, 0
输出：0
输入：空链表, 空链表
输出：空链表暴力解法：转换为数组排序
最直观的想法可能是：把两个链表的值都放到一个数组里，排序后再创建新链表。这种方法虽然不够优雅，但对于理解问题很有帮助。
暴力解法实现
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 创建数组存储所有节点值
List<Integer> values = new ArrayList<>();
// 遍历第一个链表
while (list1 != null) {
values.add(list1.val);
list1 = list1.next;
}
// 遍历第二个链表
while (list2 != null) {
values.add(list2.val);
list2 = list2.next;
}
// 排序数组
Collections.sort(values);
// 构建新链表
ListNode dummy = new ListNode(0);// 哨兵节点
ListNode current = dummy;
// 根据排序后的数组创建新链表
for (int value : values) {
current.next = new ListNode(value);
current = current.next;
}
return dummy.next;
}优化解法：双指针遍历
既然输入的链表已经排好序，我们完全可以模拟整理收据的过程：同时遍历两个链表，每次选择较小的节点连接到结果链表中。这就像拉链一样，将两个有序序列合并成一个。
代码实现与详解
public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 创建哨兵节点，简化边界情况处理 ListNode dummy = new ListNode(0); ListNode current = dummy; // 当两个链表都不为空时，比较并连接 while (list1 != null && list2 != null) { if (list1.val
页:
[1]