Posted on

Merge K Sorted Lists

https://leetcode.com/problems/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 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)
  1. 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!