You are given an array of k linked lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.
Table of Contents
Sample Input/Output:
Sample input:
lists = [
1 -> 4 -> 5,
1 -> 3 -> 4,
2 -> 6
]
Expected Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Explanation:
For the given input lists, there are three linked lists with the following values:
- 1 -> 4 -> 5
- 1 -> 3 -> 4
- 2 -> 6
After merging all the linked lists, we get the sorted linked list: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.
Time and Space Complexity:
The time complexity of the solution will be O(N log k), where N is the total number of elements in all linked lists, and k is the number of linked lists. The time complexity is dominated by the heapify operation in the priority queue, which takes O(log k) time.
The space complexity will be O(k) to store the priority queue.
C++ Solution:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
struct CompareNodes {
bool operator()(const ListNode* a, const ListNode* b) const {
return a->val > b->val; // Min-heap based on node values
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, CompareNodes> minHeap;
// Push the heads of all linked lists into the min-heap
for (ListNode* head : lists) {
if (head) {
minHeap.push(head);
}
}
ListNode* dummyHead = new ListNode(0);
ListNode* current = dummyHead;
while (!minHeap.empty()) {
ListNode* smallestNode = minHeap.top();
minHeap.pop();
current->next = smallestNode;
current = current->next;
if (smallestNode->next) {
minHeap.push(smallestNode->next);
}
}
return dummyHead->next;
}
// Function to create a linked list from a vector
ListNode* createLinkedList(vector<int>& values) {
ListNode* dummyHead = new ListNode(0);
ListNode* current = dummyHead;
for (int val : values) {
current->next = new ListNode(val);
current = current->next;
}
return dummyHead->next;
}
// Function to print the linked list
void printLinkedList(ListNode* head) {
while (head) {
cout << head->val;
if (head->next) cout << " -> ";
head = head->next;
}
cout << endl;
}
int main() {
vector<vector<int>> values = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
vector<ListNode*> lists;
// Create linked lists from the vectors
for (auto& value : values) {
lists.push_back(createLinkedList(value));
}
ListNode* mergedList = mergeKLists(lists);
cout << "Merged Linked List: ";
printLinkedList(mergedList);
return 0;
}
In this implementation, we use a priority queue (min-heap) to efficiently merge the sorted linked lists. The ListNode struct represents the nodes of the linked list, and the CompareNodes struct defines a custom comparison operator for the priority queue based on the node values.
The mergeKLists function creates a min-heap and pushes the heads of all linked lists into the heap. Then, it repeatedly extracts the smallest node from the heap, links it to the merged list, and moves the corresponding linked list’s pointer to the next node in the sorted order. This process continues until all nodes are merged.
The createLinkedList function creates a linked list from a vector of values, and the printLinkedList function prints the values of the linked list.
The main function demonstrates the usage of mergeKLists by merging the linked lists represented by the values vector and prints the result.
The output for the provided test case will be:
Merged Linked List: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6