07. Merge K Sorted Linked Lists
✅ GFG solution to merge K sorted linked lists: combine multiple sorted linked lists into one using min heap and divide & conquer approaches. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array arr[] of n sorted linked lists of different sizes. Your task is to merge all these lists into a single sorted linked list and return the head of the merged list.
Each linked list is already sorted in ascending order. The goal is to efficiently combine them while maintaining the sorted order of elements.
📘 Examples
Example 1
Input: arr[] = [[1, 3, 7], [2, 4, 8], [9]]
Output: 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9
Explanation: The arr[] has 3 sorted linked lists of size 3, 3, 1.
1st list: 1 -> 3 -> 7
2nd list: 2 -> 4 -> 8
3rd list: 9
The merged list will be: 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9Example 2
Input: arr[] = [[1, 3], [8], [4, 5, 6]]
Output: 1 -> 3 -> 4 -> 5 -> 6 -> 8
Explanation: The arr[] has 3 sorted linked lists of size 2, 1, 3.
1st list: 1 -> 3
2nd list: 8
3rd list: 4 -> 5 -> 6
The merged list will be: 1 -> 3 -> 4 -> 5 -> 6 -> 8🔒 Constraints
$1 \le \text{total no. of nodes} \le 10^5$
$1 \le \text{node->data} \le 10^3$
✅ My Approach
The optimal approach uses a Min Heap (Priority Queue) to efficiently merge k sorted linked lists by always selecting the smallest element among the current heads of all lists:
Min Heap + Priority Queue
Initialize Min Heap:
Create a min heap (priority queue) that orders nodes by their data values.
Add the head nodes of all non-empty linked lists to the heap.
Build Result List:
Create a dummy node to simplify list construction.
Use a tail pointer to track the end of the result list.
Extract and Process:
While heap is not empty:
Extract the node with minimum value from heap.
Append it to the result list.
If the extracted node has a next node, add it to the heap.
Continue Until Complete:
Repeat until all nodes are processed and heap becomes empty.
Return the head of the merged list (dummy.next).
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n log k), where n is the total number of nodes across all lists and k is the number of linked lists. Each node is inserted and extracted from the heap once, and heap operations take O(log k) time.
Expected Auxiliary Space Complexity: O(k), where k is the number of linked lists. The heap stores at most k nodes at any time (one from each list).
🧑💻 Code (C++)
class Solution {
public:
Node* mergeKLists(vector<Node*>& arr) {
auto cmp = [](Node* a, Node* b) { return a->data > b->data; };
priority_queue<Node*, vector<Node*>, decltype(cmp)> pq(cmp);
for (Node* head : arr) if (head) pq.push(head);
Node dummy(-1), *tail = &dummy;
while (!pq.empty()) {
Node* node = pq.top(); pq.pop();
tail->next = node; tail = node;
if (node->next) pq.push(node->next);
}
return dummy.next;
}
};☕ Code (Java)
class Solution {
Node mergeKLists(Node[] arr) {
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.data - b.data);
for (Node head : arr) if (head != null) pq.offer(head);
Node dummy = new Node(-1), tail = dummy;
while (!pq.isEmpty()) {
Node node = pq.poll();
tail.next = node; tail = node;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}
}🐍 Code (Python)
import heapq
class Solution:
def mergeKLists(self, arr):
heap = []
for i, head in enumerate(arr):
if head: heapq.heappush(heap, (head.data, i, head))
dummy = Node(-1)
tail = dummy
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next: heapq.heappush(heap, (node.next.data, i, node.next))
return dummy.next🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated