链表 21.合并两个排序的链表
力扣21题 将两个有序链表合并为一个新的有序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4
- 1、自己写的， 也是官方的迭代方法
时间复杂度：O(n)，空间复杂度：xx
var mergeTwoLists = function (l1, l2) {
// 得到head
var head = new ListNode(-1);
var temp = head;
// 判断需要注意需要两个链表对比的值同时存在才不会报错
while (l1 != null && l2 != null) {
// 设置当前节点的值
let bool = l1.val > l2.val;
temp.next = bool ? l2 : l1;
// 入参往后一位
l2 = bool ? l2.next : l2;
l1 = bool ? l1 : l1.next;
// 存储的结果往下一位
temp = temp.next;
// 以前写的 if 判断，我觉得上面的比较简洁
// if (l1.val <= l2.val) {
// temp.next = l1;
// l1 = l1.next;
// } else {
// temp.next = l2;
// l2 = l2.next;
// }
}
// 跳出循环后，其中哪个链表还没遍历完直接续补上去
temp.next = l1 == null ? l2 : l1;
return head.next
};
- 2.方法：递归
时间复杂度：O(n)，空间复杂度：xx
想法：两个链表头部较小的一个与剩下所有元素的 merge 操作（利用递归）结果合并。
算法：
边界情况：如果 l1 或者 l2 是 null，那么没有节点需要比较大小，所以我们只需要返回另一个非空链表。
常态情况：我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。
结束条件：如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。
var mergeTwoLists = function (l1, l2) {
// 判断当前是不是在链表的尾部 - 退出递归条件
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
// 将当前较小值抛出，next 继续往后递归
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}