Author: Robert Baindourov

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 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: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

The sum of lists[i].length will not exceed 10<sup>4</sup>.

k == lists.length

0 <= k <= 10<sup>4</sup>

0 <= lists[i].length <= 500

-10<sup>4</sup> <= lists[i][j] <= 10<sup>4</sup>

lists[i] is sorted in ascending order.

Problem Solution:

Key Idea:

1. Each linked list is already sorted.
2. By leveraging a min-heap, we can efficiently extract the smallest element among all the k linked lists and insert it into the result list.

Approach:

Steps:

1. Min-Heap:
   • Use a min-heap to store the smallest current node of each linked list.
   • The heap will always give us the smallest node among the current heads of all linked lists.
2. Input Nodes to the Heap:
   • Initially push the head of each linked list into the heap. Use the values of the nodes for comparison.
3. Merge Process:
   • Continuously extract the smallest node from the heap.
   • Append this node to the resulting linked list.
   • If the extracted node has a next node, push the next node to the heap.
4. Output:
   • After the heap is empty, the resulting linked list will be fully sorted.

Algorithm Complexity:

• Time Complexity:
  • Inserting into and extracting from the min-heap takes O(log k) time (where k is the number of linked lists).
  • There are a total of n nodes across all linked lists, so the overall complexity is O(n log k).
• Space Complexity:
  • The heap stores at most k nodes at any time, so the space complexity is O(k).

Implementation in C++:

Here is the efficient implementation using a min-heap:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Definition for a singly-linked list node
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) {}
};

// Comparator for the min-heap (to compare ListNode values)
struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // Min-Heap (smallest value first)
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // Min-Heap to store the nodes
    priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;

    // Step 1: Push the head of each linked list into the min-heap
    for (auto list : lists) {
        if (list) { // Only non-empty lists
            minHeap.push(list);
        }
    }

    // Step 2: Create a dummy node to construct the merged linked list
    ListNode* dummy = new ListNode(-1);
    ListNode* current = dummy;

    // Step 3: Pop from heap and build the merged linked list
    while (!minHeap.empty()) {
        ListNode* node = minHeap.top();
        minHeap.pop();

        // Add the smallest node to the result list
        current->next = node;
        current = current->next;

        // If there is a next node for the current list, push it into the heap
        if (node->next) {
            minHeap.push(node->next);
        }
    }

    return dummy->next; // Return the merged linked list
}

// Utility function to print a linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

int main() {
    // Example lists: [[1,4,5], [1,3,4], [2,6]]
    ListNode* list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
    ListNode* list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
    ListNode* list3 = new ListNode(2, new ListNode(6));

    vector<ListNode*> lists = {list1, list2, list3};

    ListNode* mergedList = mergeKLists(lists);

    cout << "Merged Linked List: ";
    printList(mergedList);

    return 0;
}

Explanation of Code:

1. Struct ListNode:
   • Represents a linked list node with value val and a pointer to next.
2. Heap Comparator:
   • The Compare struct defines a custom comparator to make the priority queue behave like a min-heap based on ListNode values.
3. Heap Initialization:
   • Push the first node (head) of each list into the priority queue (minHeap).
4. Merge Process:
   • As long as there are elements in the heap:
     • Extract the smallest node.
     • Append it to the result list.
     • If the extracted node has a next node, push it into the heap.
5. Print Function:
   • A utility function to print the merged linked list.

Complexity Analysis:

1. Time Complexity:
   • Let n represent the total number of nodes in all linked lists and k represent the number of linked lists.
   • Each heap insertion or extraction operation takes O(log k). Since there are n nodes total, the overall time complexity is:

     O(n log k)

2. Space Complexity:
   • The heap has a maximum size of k (the number of linked lists). Thus, the space complexity is:

     O(k)

Example Run:

Input:

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

Execution:

• Min-Heap initialization: Push [1,1,2] into the heap.
• Extract 1 → Add to result → Push 4.
• Extract 1 → Add to result → Push 3.
• Extract 2 → Add to result → Push 6.
• Merge continues…

Output:

Merged Linked List: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> nullptr

Edge Cases:

1. Empty List of Lists:
   • Input: lists = []
   • Output: nullptr
2. All Lists are Empty:
   • Input: lists = [nullptr, nullptr]
   • Output: nullptr
3. Single List:
   • Input: lists = [[1, 2, 3]]
   • Output: 1 -> 2 -> 3 -> nullptr
4. Different Length Lists:
   • Input: lists = [[1, 3], [2, 6, 7, 8], [0, 9]]
   • Handles varying lengths.

This approach efficiently merges k sorted linked lists using a min-heap (priority queue) and is well-suited for larger inputs. Let me know if you need further clarifications or assistance!