#23
Merge k Sorted Lists
Hard Min-heap of list heads
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Merge k sorted linked lists into one sorted linked list.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: merge k sorted lists.
Why this works: the next node is the smallest current head; a min-heap returns it in O(log k).
Example: [1→4→5, 1→3→4, 2→6]
heap {1, 1, 2} → take 1, push 4 …1→1→2→3→4→4→5→6
✦Hints open one at a time
The next node of the result is always the smallest current head among the k lists.
A min-heap gives the smallest head in O(log k).
↗Approach
Push every non-null head into a PriorityQueue ordered by value. Repeatedly poll the smallest, append it, and push its next node if it exists.
</>Solution (Java)
import java.util.*;
/**
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode l : lists) if (l != null) pq.add(l);
ListNode dummy = new ListNode(0), tail = dummy;
while (!pq.isEmpty()) {
ListNode n = pq.poll(); // smallest current head
tail.next = n;
tail = n;
if (n.next != null) pq.add(n.next);
}
return dummy.next;
}
}!Common mistake
Merging lists one after another into a growing result — O(N·k).
Complexity
- Time: O(N log k), N = total nodes.
- Space: O(k).
Topic: Linked List
🎬 Episodes 40–45: video coming soon