力扣: 合并两个有序链表

2025/6/7 10:43:32 来源：https://blog.csdn.net/Snowyyds/article/details/141813466 浏览: 次关键词：力扣: 合并两个有序链表

文章目录

需求
分析
结尾

在这里插入图片描述

需求

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
在这里插入图片描述

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

分析

代码:

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if( list1 == null || list2 == null ){return list1 == null ? list2 : list1;}ListNode preHead = new ListNode(-1);ListNode cur = preHead;while( true ){if( list1.val < list2.val ){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;if( list1 == null ){cur.next = list2;break;}if( list2 == null ){cur.next = list1;break;}}return preHead.next;
}

代码解释:

处理空链表的情况

if (list1 == null || list2 == null) {return list1 == null ? list2 : list1;
}

如果 list1 或 list2 其中之一为 null，则直接返回另一个链表，因为合并的结果就是另一个链表。

创建一个新链表的头节点

ListNode preHead = new ListNode(-1);
ListNode cur = preHead;

preHead 是一个虚拟头节点，用于简化后续操作，cur 指向当前的合并链表的尾部节点，初始时它指向虚拟头节点 preHead。
合并两个链表

while (true) {if (list1.val < list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}cur = cur.next;
}

进入一个无限循环，比较 list1 和 list2 的当前节点值：
如果 list1 的值小于 list2 的值，说明 list1 的节点应当先加入合并链表。
将 cur 的 next 指向 list1，然后将 list1 移动到下一个节点。
如果 list1 的值不小于 list2，则将 cur 的 next 指向 list2 并移动 list2。
处理剩余节点

cur = cur.next;
if (list1 == null) {cur.next = list2;break;
}
if (list2 == null) {cur.next = list1;break;
}

每次循环结束后，将 cur 移动到下一个节点。
检查 list1 或 list2 是否已经遍历完：
如果 list1 为 null，将 cur.next 指向 list2（因为 list2 尚未遍历完），然后退出循环。
如果 list2 为 null，将 cur.next 指向 list1，然后退出循环。
返回合并后的链表