23. Merge k Sorted Lists

📝 Problem Details

• Title: 23. Merge k Sorted Lists
• **Link:**https://leetcode.com/problems/merge-k-sorted-lists/
• Difficulty: Hard
• Tags/Categories: Linked-List Priority-Queue

💭What Were My Initial Thoughts?

- given k linked lists
- each list is sorted
- merge all linked lists into one sorted linked list and return it 

number of lists can be between 0 and 10^4

- naive inefficient approach:
	- for each node in every k list we could insert the values into a priority queue
	- once the priority queue is fully populated we could construct a new list and construct a new node for each element in the queue

- optimization:
	- maybe instead of constructing new nodes we can create a custom compare funciton for the priority queue that orders the nodes themselves rather than the values and we just assign the pointers in the reconstruction phase

💡 Explanation of Solution

same as optimized approach

⌛ Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

💻 Implementation of Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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)> minHeap(compare);
 
        for(auto list : lists) {
            if(list) minHeap.push(list);
        }
 
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
 
        while(!minHeap.empty()) {
            ListNode* minNode = minHeap.top();
            minHeap.pop();
            current->next = minNode;
            current = current->next;
 
            if(minNode->next) {
                minHeap.push(minNode->next);
            }
        }
 
        return dummy->next;
    }
};