要点:递归、链表
描述
1 2 3 4 5 6
| 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
|
题解
方法一
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
var mergeTwoLists = function(l1, l2) { var mergedHead = { val : -1, next : null }, crt = mergedHead; if (l1 === null) return l2; if (l2 === null) return l1; while(l1 && l2) { if (l1.val > l2.val) { crt.next = l2 l2 = l2.next } else { crt.next = l1 l1 = l1.next } crt = crt.next } crt.next = l1 || l2 return mergedHead.next };
|
- 208/208 cases passed (80 ms)
- Your runtime beats 72.12 % of javascript submissions
- Your memory usage beats 45.4 % of javascript submissions (39.5 MB)
方法二
递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
var mergeTwoLists = function(l1, l2) { if (l1 === null) return l2; if (l2 === null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } };
|
- 208/208 cases passed (76 ms)
- Your runtime beats 84.73 % of javascript submissions
- Your memory usage beats 37.88 % of javascript submissions (39.5 MB)
时间复杂度:$O(M+N)$
空间复杂度:$O(M+N)$
M、N 是两条链表 l1、l2 的长度
方法三
迭代
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| var mergeTwoLists = function (l1, l2) { const prehead = new ListNode(-1);
let prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } prev.next = l1 === null ? l2 : l1; /prev.next = l1 || l2;
return prehead.next; };
|
- 208/208 cases passed (96 ms)
- Your runtime beats 26.02 % of javascript submissions
- Your memory usage beats 44.47 % of javascript submissions (39.5 MB)
Tips:
Please indicate the source and original author when reprinting or quoting this article.