Problem
Given an array of k linked lists, where each linked list is sorted in ascending order, merge all the lists into one sorted linked list.Return the head of the merged sorted linked list.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
lists = [ 1 → 4 → 5, 1 → 3 → 4, 2 → 6 ] Output
1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 Solution
This solution uses a Min Heap to efficiently select the smallest node among the current nodes of all linked lists.The first node of each non-empty list is added to the heap. The smallest node is then removed and added to the merged list. If that node has a next node, the next node is added to the heap.
This process continues until the heap becomes empty, ensuring that nodes are added to the result in sorted order.
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
(a, b) -> Integer.compare(a.val, b.val)
);
// Add the first node of each list.
for (ListNode node : lists) {
if (node != null) {
minHeap.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (!minHeap.isEmpty()) {
// Get the smallest node.
ListNode node = minHeap.poll();
current.next = node;
current = current.next;
// Add the next node from the same list.
if (node.next != null) {
minHeap.offer(node.next);
}
}
return dummy.next;
}
Complexity
Let N be the total number of nodes across all linked lists and k be the number of lists. Each node is added to and removed from the Min Heap once, and each heap operation takesO(log k) time. Therefore, the overall time complexity is
O(N log k). The heap stores at most k nodes at a time, resulting in O(k) extra space.