友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
思路分析
优先队列是最优解，退而求其次，可以考虑使用分治。
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
48
49
50
51
52
53
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
for (ListNode l : lists) {
if (Objects.nonNull(l)) {
heap.add(l);
}
}
ListNode dummy = new ListNode();
ListNode curr = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
curr.next = node;
curr = curr.next;
if (Objects.nonNull(node.next)) {
heap.add(node.next);
}
}
return dummy.next;
}
/**
* Runtime: 40 ms, faster than 20.21% of Java online submissions for Merge k Sorted Lists.
*
* Memory Usage: 39.6 MB, less than 74.87% of Java online submissions for Merge k Sorted Lists.
*/
public ListNode mergeKLists1(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
for (ListNode list : lists) {
if (Objects.nonNull(list)) {
queue.add(list);
}
}
ListNode result = null;
ListNode tail = null;
for (ListNode node = queue.poll(); Objects.nonNull(node); ) {
if (Objects.isNull(result)) {
result = node;
}
ListNode next = node.next;
if (Objects.nonNull(next)) {
queue.add(next);
}
if (Objects.nonNull(tail)) {
tail.next = node;
}
tail = node;
node = queue.poll();
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode mergeKLists(ListNode[] lists) {
if (Objects.isNull(lists) || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
for (ListNode node : lists) {
if (node != null) {
queue.offer(node);
}
}
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (!queue.isEmpty()) {
ListNode node = queue.poll();
cur.next = node;
cur = cur.next;
if (node.next != null) {
queue.offer(node.next);
}
}
return dummy.next;
}