Merge k Sorted Lists hard

Problem Statement

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example 1

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 into one sorted list: 1->1->2->3->4->4->5->6

Example 2

Input: lists = [] Output: []

Steps

1. Handle Empty Input: If the input list lists is empty, return an empty list.

2. Choose a Merge Strategy: We'll use a priority queue (min-heap) to efficiently merge the lists.

3. Initialize Priority Queue: Create a min-heap that stores tuples of the form (node->val, node), where node is a node from one of the input lists. Initially, add the first node from each non-empty input list to the heap.

4. Iterative Merging: While the heap is not empty:

   • Extract the minimum element (node with smallest value) from the heap.
   • Append the node's value to the result list.
   • If the extracted node has a next node, add the next node to the heap.

5. Return Result: Return the sorted linked list constructed in step 4.

Explanation

The key to solving this problem efficiently is using a priority queue (min-heap). A min-heap allows us to quickly find the smallest element among all the lists. By repeatedly extracting the smallest element and adding its successor (if it exists), we build the merged sorted list. This approach avoids the need for pairwise merging of lists, which would have a higher time complexity.

Code

#include <iostream>
#include <vector>
#include <queue>

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) {}
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;

    std::priority_queue<std::pair<int, ListNode*>, std::vector<std::pair<int, ListNode*> >, std::greater<std::pair<int, ListNode*> > > pq;

    // Add the first node of each list to the priority queue
    for (ListNode* list : lists) {
        if (list != nullptr) {
            pq.push({list->val, list});
        }
    }

    ListNode* dummy = new ListNode();
    ListNode* tail = dummy;

    while (!pq.empty()) {
        ListNode* curr = pq.top().second;
        pq.pop();
        tail->next = curr;
        tail = tail->next;

        if (curr->next != nullptr) {
            pq.push({curr->next->val, curr->next});
        }
    }

    return dummy->next;
}


int main() {
    // Example usage:
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(5);

    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);

    ListNode* l3 = new ListNode(2);
    l3->next->next = new ListNode(6);

    std::vector<ListNode*> lists = {l1, l2, l3};
    ListNode* mergedList = mergeKLists(lists);

    while (mergedList != nullptr) {
        std::cout << mergedList->val << " ";
        mergedList = mergedList->next;
    }
    std::cout << std::endl; // Output: 1 1 2 3 4 4 5 6

    return 0;
}

Complexity

• Time Complexity: O(N log k), where N is the total number of nodes across all k lists. This is because we add and remove each node from the priority queue at most once. The priority queue operations (insertion and extraction) take O(log k) time.

• Space Complexity: O(k), where k is the number of linked lists. This is the space used by the priority queue to store the smallest node from each list. In the worst case, all k lists can have their first nodes in the heap at the same time.