Sponsored
Sponsored
This approach utilizes a min-heap (priority queue) to efficiently merge k sorted linked lists. The heap will help us identify the minimum element among the lists efficiently.
This ensures that the smallest elements are appended to the resulting list in sorted order.
Time Complexity: O(N log k), where N is the total number of nodes and k is the number of linked lists. Each insertion and extraction from the heap takes log k time, and there are N nodes in total.
Space Complexity: O(k), due to the heap that at most stores one node from each list.
1import heapq
2
3class ListNode:
4 def __init__(self, x):
5 self.val = x
6 self.next = None
7
8 # For min-heap comparison
9 def __lt__(self, other):
10 return self.val < other.val
11
12class Solution:
13 def mergeKLists(self, lists):
14 if not lists or len(lists) == 0:
15 return None
16 heap = []
17 for l in lists:
18 if l:
19 heapq.heappush(heap, l)
20 dummy = ListNode(0)
21 current = dummy
22 while heap:
23 node = heapq.heappop(heap)
24 current.next = node
25 current = current.next
26 if node.next:
27 heapq.heappush(heap, node.next)
28 return dummy.nextThe Python solution uses the built-in heapq module which provides an efficient priority queue implementation. Each ListNode is wrapped so that it is comparable based on its val, allowing the heap operations to work correctly. The solution maintains a heap of size k, thus ensuring efficient merging.
This approach follows the divide-and-conquer methodology to merge the lists incrementally.
Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists.
Space Complexity: O(log k) for recursion stack space.
1#include <vector>
2using namespace std;
3
4struct ListNode {
5 int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
return mergeKLists(lists, 0, lists.size() - 1);
}
private:
ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right) {
if (left == right) return lists[left];
int mid = (right + left) / 2;
ListNode* l1 = mergeKLists(lists, left, mid);
ListNode* l2 = mergeKLists(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* last = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
last->next = l1;
l1 = l1->next;
} else {
last->next = l2;
l2 = l2->next;
}
last = last->next;
}
last->next = l1 ? l1 : l2;
return dummy.next;
}
};The C++ solution uses a divide-and-conquer strategy to break down the problem into smaller instances, which are solved recursively. The two halves of the list array are merged progressively, much like the merge step in merge sort.