题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
1
2
3
4
5
| [
1->4->5,
1->3->4,
2->6
]
|
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
提示：
1
2
3
4
5
6
| k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
|
我的解答
写过合并两个链表的题，合并多个就两两合并即可。
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
| public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0 ){
return null;
}
if(lists.length == 1){
return lists[0];
}
ListNode p = lists[0];
for (int i= 1;i<lists.length;i++) {
p = mergeTwoLists(p,lists[i]);
}
return p;
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode p = dummy, p1=list1,p2=list2;
while(p1 != null && p2 != null){
if(p1.val > p2.val){
p.next = p2;
p2 = p2.next;
}else{
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
if(p1 == null){
p.next = p2;
}
if(p2 == null){
p.next = p1;
}
return dummy.next;
}
|
上面其实就是运用了分治的思想。
如果要按两个链表的处理思路，就是需要能对比出k个链表各个移动指针的最小值。我看评论都是利用 PriorityQueue。
但是如果使用PriorityQueue，那为什么不把所有数据都放进去，从最小的一个个的取出组成链表呢？
试一下当然是可以的：
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
| public ListNode mergeKListsUsePriorityQueue(ListNode[] lists) {
if(lists.length == 0 ){
return null;
}
if(lists.length == 1){
return lists[0];
}
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e.val));
ListNode p = null;
for (ListNode list : lists) {
p = list;
while (p!= null){
queue.add(p);
p = p.next;
}
}
ListNode head = new ListNode();
p = head;
while (!queue.isEmpty()){
p.next = queue.poll();
p = p.next;
p.next = null;
}
return head.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
| class Solution {
class Status implements Comparable<Status> {
int val;
ListNode ptr;
Status(int val, ListNode ptr) {
this.val = val;
this.ptr = ptr;
}
public int compareTo(Status status2) {
return this.val - status2.val;
}
}
PriorityQueue<Status> queue = new PriorityQueue<Status>();
public ListNode mergeKLists(ListNode[] lists) {
for (ListNode node: lists) {
if (node != null) {
queue.offer(new Status(node.val, node));
}
}
ListNode head = new ListNode(0);
ListNode tail = head;
while (!queue.isEmpty()) {
Status f = queue.poll();
tail.next = f.ptr;
tail = tail.next;
if (f.ptr.next != null) {
queue.offer(new Status(f.ptr.next.val, f.ptr.next));
}
}
return head.next;
}
}
|
链接：https://leetcode.cn/problems/merge-k-sorted-lists