Merge K Sorted Lists
You are given an array of k linked-lists, where each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Constraints:
- 1 <= k <= 10^4
- 0 <= Node.val <= 10^4
- 0 <= lists.length <= 10^4
- lists[i] has at most 10^4 nodes
- It is guaranteed that the answer will be unique (i.e., the sum of all node values will not exceed 10^7).
Examples:
Input: [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The first linked-list is [1,4,5], the second linked-list is [1,3,4], and the third linked-list is [2,6]. The merged linked-list is [1,1,2,3,4,4,5,6].
Solutions
Priority Queue
We use a priority queue to store the current smallest node from each linked-list. We start by pushing the head of each linked-list into the priority queue. Then, we pop the smallest node from the priority queue and add it to the result linked-list. We also she,Question and the priority queue is empty.
import java.util.PriorityQueue;
public
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode list : lists) {
if (list != null) {
minHeap.add(list);
}
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!minHeap.isEmpty()) {
ListNode node = minHeap.poll();
curr.next = node;
curr = curr.next;
if (node.next != null) {
minHeap.add(node.next);
}
}
return dummy.next;
}
}Follow-up:
How would you optimize the solution if the linked-lists are very large and do not fit into memory?
