迭代 + 虚拟头结点
解题思路
定义一个哨兵节点 dummy ，使用 dummy.next 来保存需要返回的头节点；
判断 l1 和 l2 哪个更小，就把这个节点接到 dummy 下一个；
直到有一边为 null ，即可将另一边剩余的都接到 dummy 上；
复杂度
-
时间复杂度：
O(n + m)，其中 n 和 m 分别为两个链表的长度；因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和；所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为O(n+m)； -
空间复杂度：
O(1)
代码实现
var mergeTwoLists = function (list1, list2) {
let dmy = new ListNode(0, null);
let curr = dmy;
while (list1 && list2) {
if (list1.val < list2.val) {
curr.next = list1;
list1 = list1.next;
} else {
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
if (list1 === null) curr.next = list2;
if (list2 === null) curr.next = list1;
return dmy.next;
};
递归
解题思路
递归边界：如果其中一个链表为空，直接返回另一个链表作为合并后的结果；
如果两个链表都不为空，则比较两个链表当前节点的值，并选择较小的节点作为新链表的当前节点；例如 list1 的节点值更小，那么递归调用
mergeTwoLists(list1.next, list2)，将递归返回的链表接在 list1 的末尾；
图解
复杂度
-
时间复杂度：
O(n + m)，其中 n 和 m 分别为两个链表的长度；因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和；所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为O(n+m)； -
空间复杂度：
O(n + m)，其中 n 和 m 分别为两个链表的长度；
代码实现：
var mergeTwoLists = function (list1, list2) {
if (list1 === null) return list2;
if (list2 === null) return list1;
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
list2.next = mergeTwoLists(list1, list2.next);
return list2;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 445. 两数相加 II
上一篇
评论
