合并K个升序链表
题目介绍
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
1
2
3
4
5
6
7
8
9
10
| 输入：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：
示例 3：
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
这里：元素为[]在java就是null，列表为空就是数组大小为空。
题目解法
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| package algorithm;
public class MergeKSortedLists {
public static ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
ListNode head = new ListNode(Integer.MAX_VALUE);
ListNode cur = head;
ListNode prev = cur;
int index = -1;
while (true) {
int count = 0;
for (int i = 0; i < lists.length; i++) {
if (lists[i] == null) {
count ++;
if (count == lists.length && index > -1) {
prev.next = null;
return head;
} else if (count == lists.length) {
return null;
}
continue;
}
if (lists[i] != null && lists[i].val <= cur.val) {
cur.val = lists[i].val;
index = i;
}
}
if (lists[index] != null) {
lists[index] = lists[index].next;
}
cur.next = new ListNode(Integer.MAX_VALUE);
prev = cur;
cur = cur.next;
}
}
public static void main(String[] args) {
ListNode a1 = new ListNode(1);
ListNode a2 = new ListNode(4);
a1.next = a2;
ListNode a3 = new ListNode(5);
a2.next = a3;
ListNode a4 = new ListNode(1);
ListNode a5 = new ListNode(3);
a4.next = a5;
ListNode a6 = new ListNode(4);
a5.next = a6;
ListNode a7 = new ListNode(2);
ListNode a8 = new ListNode(6);
a7.next = a8;
ListNode[] lists = new ListNode[]{a1, a4, a7};
print(mergeKLists(lists));
}
private static void print(ListNode node) {
while (node != null) {
System.out.print(node.val);
node = node.next;
}
System.out.println();
}
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
|
打印：
思路：
这道题依然想出了三种思路，大致对应了官方的三种思路。第一种：一个一个合并，直到结束；第二种思路，就是两两归并，没想到效率这么高，所以计算复杂度是需要考虑到的；第三种，也是自己给出的结果，效率不是很理想，参考了官方答案，没想到用了PriorityQueue，利用优先队列本身的排序机制（小顶堆），非常巧妙。