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:
- Each linked list is already sorted.
- 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:
- 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.
- Input Nodes to the Heap:
- Initially push the head of each linked list into the heap. Use the values of the nodes for comparison.
- 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.
- 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).
- Inserting into and extracting from the min-heap takes O(log k) time (where
- Space Complexity:
- The heap stores at most
k
nodes at any time, so the space complexity is O(k).
- The heap stores at most
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:
- Struct
ListNode
:- Represents a linked list node with value
val
and a pointer tonext
.
- Represents a linked list node with value
- Heap Comparator:
- The
Compare
struct defines a custom comparator to make the priority queue behave like a min-heap based onListNode
values.
- The
- Heap Initialization:
- Push the first node (head) of each list into the priority queue (
minHeap
).
- Push the first node (head) of each list into the priority queue (
- 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.
- As long as there are elements in the heap:
- Print Function:
- A utility function to print the merged linked list.
Complexity Analysis:
- Time Complexity:
- Let
n
represent the total number of nodes in all linked lists andk
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:
- Let
O(n log k)
- Space Complexity:
- The heap has a maximum size of
k
(the number of linked lists). Thus, the space complexity is:
- The heap has a maximum size of
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 → Push4
. - Extract
1
→ Add to result → Push3
. - Extract
2
→ Add to result → Push6
. - Merge continues…
Output:
Merged Linked List: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> nullptr
Edge Cases:
- Empty List of Lists:
- Input:
lists = []
- Output:
nullptr
- Input:
- All Lists are Empty:
- Input:
lists = [nullptr, nullptr]
- Output:
nullptr
- Input:
- Single List:
- Input:
lists = [[1, 2, 3]]
- Output:
1 -> 2 -> 3 -> nullptr
- Input:
- Different Length Lists:
- Input:
lists = [[1, 3], [2, 6, 7, 8], [0, 9]]
- Handles varying lengths.
- Input:
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!