Merge K Sorted Lists
Merging k sorted lists is a classic problem that can be solved efficiently using a min-heap. Place the head of each list into a min-heap, then repeatedly extract the smallest and push the next node from that list.
Algorithm:
1. Create a min-heap (PriorityQueue) of Node objects, ordered by value.
2. Add the head of each list to the heap.
3. While heap not empty, pop the smallest node, add it to result, and if that node has a next, push it into the heap.
Java implementation (for ListNode):
public static ListNode mergeKLists(ListNode[] lists) {
PriorityQueue heap = new PriorityQueue<>((a,b) -> a.val - b.val);
for (ListNode head : lists) {
if (head != null) heap.offer(head);
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
ListNode smallest = heap.poll();
tail.next = smallest;
tail = tail.next;
if (smallest.next != null) heap.offer(smallest.next);
}
return dummy.next;
}
Complexity: O(N log k) where N is total number of nodes and k is number of lists.
Two Minute Drill
- Merge k sorted lists using min-heap of size k.
- Extract smallest, push its next.
- Time O(N log k), space O(k).
- Efficient for merging multiple sorted sequences.
Need more clarification?
Drop us an email at career@quipoinfotech.com