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.
struct compare {
bool operator()(const ListNode* a, const ListNode* b) {
return a->val > b->val;
}
}
;
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> minHeap;
for (ListNode* list : lists) {
if (list) {
minHeap.push(list);
}
}
ListNode* dummy = new ListNode(0);
ListNode* curr = dummy;
while (!minHeap.empty()) {
ListNode* node = minHeap.top();
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?
