HARD

Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked lists into one sorted linked list and return it.

Example

Input:

lists = [[1,4,5],[1,3,4],[2,6]]

Output:

[1,1,2,3,4,4,5,6]

Explanation:
The linked lists are:

1->4->5
1->3->4
2->6

Merging them yields 1->1->2->3->4->4->5->6.

Constraints

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
All the lists are sorted in ascending order.

Solution: Min Heap (Priority Queue)

Time Complexity: O(N log k), where N is the total number of nodes.
Space Complexity: O(k) for the heap.

C++

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto compare = [&](ListNode* a, ListNode* b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> pq(compare);
        for(auto l : lists) 
            if (l) pq.push(l);
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(pq.size()) {
            cur->next = pq.top();
            pq.pop();
            cur = cur->next;
            if (cur->next) pq.push(cur->next);
        }
        return dummy->next;
    }
};