Merge k Sorted Lists
Source
Merge k sorted linked lists and return it as one sorted list.
Analyze and describe its complexity.
Example
Given lists:
[
2->4->null,
null,
-1->null
],
return -1->2->4->null.
Java
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
if (lists == null || lists.size() < 1) {
return null;
}
PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>() {
public int compare(ListNode l1, ListNode l2) {
return l1.val - l2.val;
}
});
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) != null) {
minHeap.offer(lists.get(i));
}
}
while (!minHeap.isEmpty()) {
ListNode temp = minHeap.poll();
tail.next = temp;
tail = temp;
if (temp.next != null) {
minHeap.offer(temp.next);
}
}
return dummy.next;
}
}