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.
var mergeKLists = function (lists) {
const minHeap = new MinHeap();
for (let i = 0; i < lists.length; i++) {
if (lists[i]) {
minHeap.push(lists[i]);
}
}
const dummy = new ListNode();
let curr = dummy;
while (minHeap.size > 0) {
const node = minHeap.pop();
curr.next = node;
curr = curr.next;
if (node.next) {
minHeap.push(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?
