Intermediate LevelData Structures & Algorithms
How do you merge K sorted linked lists efficiently?
ā Interview Prompt: Merge K sorted linked lists using a Min-Heap in O(N log K) time, explaining why naive K-way merge is suboptimal.
Naive: Merge one by one ā $O(NK)$ total.
Optimal: Min-Heap of size $K$ ā $O(N \log K)$
Algorithm:
1
Push the head of each of the $K$ lists into a min-heap (ordered by node value).
2
Pop the minimum node ā append to result list.
3
Push the popped node's next node (if exists) into the heap.
4
Repeat until heap is empty.
ā¢
Time: $O(N \log K)$ where $N$ = total nodes, $K$ = number of lists.
ā¢
Space: $O(K)$ for the heap.
Code Implementation Example
typescript
// Simulating with sort ā real solution needs a proper min-heap
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
const nodes: number[] = [];
for (let head of lists) {
while (head) { nodes.push(head.val); head = head.next; }
}
nodes.sort((a, b) => a - b);
const dummy = new ListNode(0);
let curr = dummy;
for (const val of nodes) { curr.next = new ListNode(val); curr = curr.next; }
return dummy.next;
}
// Proper O(N log K): push first node of each list into min-heap,
// pop min, push popped.next, repeat.š”Merge K Sorted Lists ā O(N log K) with a min-heap of size K.
šÆ Interview Key Takeaway
Min-Heap merge is O(N log K) vs O(NK) for sequential merge. This pattern appears in external sort, streaming merges, and database merge joins.
#DSA#Linked List#Heap#Merge#Intermediate
Back to all Data Structures & Algorithms Questionsā