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
| class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> deque = new LinkedList<>();
for (ListNode node : lists) {
if (node != null) {
deque.offer(node);
}
}
while (deque.size() > 1) {
ListNode nodeOne = deque.poll();
ListNode nodeTwo = deque.poll();
deque.offer(merge(nodeOne, nodeTwo));
}
return deque.size() != 0 ? deque.poll() : null;
}
private ListNode merge(ListNode nodeOne, ListNode nodeTwo) {
ListNode prev = null, currNode = nodeOne, ptr = nodeTwo;
while (currNode != null && ptr != null) {
if (currNode.val <= ptr.val) {
prev = currNode;
currNode = currNode.next;
} else {
if (prev != null) {
prev.next = ptr;
}
prev = ptr;
ptr = ptr.next;
prev.next = currNode;
}
}
if (currNode == null) {
prev.next = ptr;
}
return nodeOne.val <= nodeTwo.val ? nodeOne : nodeTwo;
}
}
|
第一种解法就是两两合并. 我们用一个queue来装node. 每次从头部拿两个合并, 合并好的再放到尾部. 我之前想的是严格按照两两合并.比如开始有偶数个, 那可以两两合并, 合并完可能出现奇数个, 这样的话会剩下一个不能合并, 但是不让这个剩下的掺和到那些它前面两两合并好的list中. 但其实不用这么严格, 剩下的这个和后面那个之前合并好的合并不就行
时间复杂度: O(nlogk) n是node的总个数, k是lists的长度. 我们每内部循环走一遍就会遍历所有的nodes, 一共要合并logk次, 因此是Nlogk
空间复杂度: O(k)
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
47
| class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> deque = new LinkedList<>();
for (ListNode node : lists) {
if (node != null) {
deque.offer(node);
}
}
while (deque.size() > 1) {
int size = deque.size();
int count = 0;
while (count < size) {
if (size - count > 1) {
ListNode nodeOne = deque.poll();
ListNode nodeTwo = deque.poll();
deque.offer(merge(nodeOne, nodeTwo));
count += 2;
} else {
deque.offer(deque.poll());
count += 1;
}
}
}
return deque.size() != 0 ? deque.poll() : null;
}
private ListNode merge(ListNode nodeOne, ListNode nodeTwo) {
ListNode prev = null, currNode = nodeOne, ptr = nodeTwo;
while (currNode != null && ptr != null) {
if (currNode.val <= ptr.val) {
prev = currNode;
currNode = currNode.next;
} else {
if (prev != null) {
prev.next = ptr;
}
prev = ptr;
ptr = ptr.next;
prev.next = currNode;
}
}
if (currNode == null) {
prev.next = ptr;
}
return nodeOne.val <= nodeTwo.val ? nodeOne : nodeTwo;
}
}
|
这个是严格一层一层的合并, 也就是两两合并, 剩下的一个就保留到下一次. 其实没必要.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> nodeQ = new PriorityQueue<>((a, b) -> a.val - b.val);
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
nodeQ.offer(lists[i]);
}
}
ListNode dummy = new ListNode(0), ptr = dummy;
while (!nodeQ.isEmpty()) {
ListNode currNode = nodeQ.poll();
ptr.next = currNode;
if (currNode.next != null) {
nodeQ.offer(currNode.next);
}
ptr = ptr.next;
}
return dummy.next;
}
}
|
这个是用priority queue. 为啥想到用PQ? 因为合并K arrays, 条件反射.
时间复杂度和空间复杂度不变.
