/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// 结合先前做的合并两个有序列表,这里可以很自然的想到,暴力一点,笨一点
// 每次只处理两个链表,慢慢来
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;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 === null ? l2 : l1;
return prehead.next;
};
let newNode = new ListNode()
// new List(Number.NEGATIVE_INFINITY),改为这样就ok了
let tempNode = newNode
while (lists.length) {
let arrNode = lists.shift()
tempNode = mergeTwoLists(tempNode, arrNode)
}
return newNode.next
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
这个版本代码的问题在于,一开始初始值是0,那就导致数组中的第一项有可能在合并后被更小的项替换,比如-1。这也是过不了[[2], [], [-1]]
这个case的原因,但是尝试往new