-
Notifications
You must be signed in to change notification settings - Fork 1
/
MergeKLists.java
44 lines (40 loc) · 1.2 KB
/
MergeKLists.java
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
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* <a href=https://leetcode-cn.com/problems/merge-k-sorted-lists/description/>
* Click to see online description
* </a>
* <br>
* In my solution, I use the PriorityQueue(min heap) to solve the problem.
*
* 23. Merge k Sorted Lists
* 最小堆(优先级队列)
* @author LBW
*/
public class MergeKLists {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode l1, ListNode l2) {
return l1.val - l2.val;
}
});
//init the queue
for (ListNode list: lists) {
if(list != null)
queue.offer(list);
}
//start to get result.
while (!queue.isEmpty()) {
ListNode minNode = queue.poll();
cur.next = new ListNode(minNode.val);
cur = cur.next;
//get the next node.
if (minNode.next != null)
queue.offer(minNode.next);
}
return dummy.next;
}
}