友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = [] 输出：[]
示例 3：
输入：lists = [[]] 输出：[]
提示：
-
k == lists.length -
0 <= k <= 104 -
0 <= lists[i].length <= 500 -
-104 <= lists[i][j] <= 104 -
lists[i]按 升序 排列 -
lists[i].length的总和不超过104
思路分析
优先队列是最优解，退而求其次，可以考虑使用分治。
-
一刷
-
二刷
-
三刷
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
54
55
56
57
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2019-10-22 12:40:12
*/
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
23
24
25
26
27
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-02 20:13:49
*/
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;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-03-30 23:20:44
*/
public ListNode mergeKLists(ListNode[] lists) {
if (Objects.isNull(lists) || lists.length == 0) {
return null;
}
// 注意：这里使用一个虚拟头节点，方便后续的操作
ListNode dummy = new ListNode(0);
// 自定义 Comparator，对堆内的 ListNode 头节点数字做排序
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
for (ListNode node : lists) {
if (Objects.nonNull(node)) {
pq.offer(node);
}
}
ListNode current = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
current.next = node;
current = node;
ListNode next = node.next;
node.next = null;
if (Objects.nonNull(next)) {
pq.offer(next);
}
}
return dummy.next;
}