49 / 75
Hard
Merge K Sorted Lists
#49linked-listheappriority-queuemerge-sortdivide-and-conquer
Use min-heap to always extract smallest element from k lists, adding next element from same list.
Example:
Input:
lists=[[1,4,5],[1,3,4],[2,6]]Output:
[1,1,2,3,4,4,5,6]Common Mistakes:
- Trying to merge lists pairwise naively (less efficient)
- Not using heap (results in O(kN) comparisons)
- Forgetting to check if node is null before adding to heap
- Not advancing pointer after adding node to result
Notes:
Heap approach: Time O(N log k) where N=total nodes, k=number of lists. Space O(k) for heap. Alternative: divide-and-conquer merging pairs.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Use min-heap to always extract smallest element from k lists, adding next element from same list.
Example:
Input:
lists=[[1,4,5],[1,3,4],[2,6]]Output:
[1,1,2,3,4,4,5,6]Common Mistakes:
- Trying to merge lists pairwise naively (less efficient)
- Not using heap (results in O(kN) comparisons)
- Forgetting to check if node is null before adding to heap
- Not advancing pointer after adding node to result
Notes:
Heap approach: Time O(N log k) where N=total nodes, k=number of lists. Space O(k) for heap. Alternative: divide-and-conquer merging pairs.
49/75
Merge K Sorted Lists