LeetCode 23 ·
Hard
Merge k Sorted Lists
Merge k sorted linked lists into one sorted list.
Try it
Step through the core mechanic. The simulator below runs the heap shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Heap — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
A min-heap of the current head from each list; pop the smallest, attach it, push its successor. Alternatively divide-and-conquer pairwise merges. Both are O(N log k).
| Aspect | Value |
|---|---|
| Pattern | Heap |
| Recognise it by | K-way merge of sorted lists. |
| Time complexity | O(N log k) |
| Space complexity | O(k) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.