1. 题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
2. 解决思路
可以使用迭代方法来实现有序链表的合并.
假设有两个有序链表 list1和list2, 当这两个链表都不是空链表时,选择头节点中较小的一个作为合并链表的头节点,.
移动有序链表的指针,比较list1和list2最新的头节点, 添加到合并链表中.
3. 关键代码
/**
* 合并两个有序列表
*
* @param list1 有序链表1, 顺序: 由小到大
* @param list2 有序链表2, 顺序: 由小到大
* @return ListNode 合并后的有序链表
*/
public static ListNode merge(ListNode list1, ListNode list2) {
// 极值判断
if (list1 == null || list2 == null) {
return list1 == null ? list2 : list1;
}
ListNode cur1 = list1; // list1中当前正在比较的头节点
ListNode cur2 = list2; // list2中当前正在比较的头节点
ListNode head = null; // 已完成合并操作的链表(默认头节点是两个有序链表头节点中较小的一个)
if (cur1.val <= cur2.val) {
head = cur1;
cur1 = cur1.next; // 更新cur1的头节点
} else {
head = cur2;
cur2 = cur2.next; // 更新cur2的头节点
}
ListNode pre = head; // 临时节点,开始指向head, 后面通过pre不断调整head节点的next属性的引用
while (cur1 != null && cur2 != null) { // 仅当两个队列当前操作的节点都不为空时,才需要进行比较与合并操作
if (cur1.val <= cur2.val) {
pre.next = cur1; // 当cur1的值小于cur2时,next指向cur1
cur1 = cur1.next; // cur1节点后移,继续后面节点的比较
} else {
pre.next = cur2; // 当cur2的值小于cur1时,将cur2作为待合并的节点
cur2 = cur2.next; // cur2节点后移,继续后面节点的比较
}
// 这一行同时也不断调整了head节点的next属性,扩充了head链表
pre = pre.next; // 链表指针后移
}
// 当其中一个链表(假设是cur1)的最后一个节点完成了合并操作,而另一个链表(假设是cur2)还有剩余节点未合并,
// 此时就需要将最后完成合并的节点(pre节点)的next指向还有节点未合并的链表(不为空的链表).
// 这一步是必须存在的,因为两个有序链表合并,必然会存在其中一个节点先完成合并.
pre.next = cur1 != null ? cur1 : cur2;
// 返回合并后,完整的有序链表
return head;
}完整测试代码:
4. 复杂度分析
时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
空间复杂度：O(1)。我们只需要常数的空间存放若干变量。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 george_95@126.com