hard
Merge k Sorted Lists
You are given k linked lists, each sorted in ascending order. Merge them into a single sorted linked list and return its head.
Constraints
- 0 ≤ k ≤ 10^4
- Total nodes ≤ 10^4 · 500
- -10^4 ≤ node value ≤ 10^4
Examples
in: lists = [[1,4,5],[1,3,4],[2,6]]
out: [1,1,2,3,4,4,5,6]
Recognition clues
- Many already-sorted inputs
- Merging two sorted lists is a known O(n) primitive
- Pairwise merging halves the number of lists each round
Pattern
Divide and ConquerIf a problem on n items can be solved from solutions on two halves plus linear-time combination work, the recurrence T(n) = 2T(n/2) + O(n) gives O(n log n). Merge sort's merge step is the template; counting inversions and merging k lists pairwise are direct instances.
Solution
Merge lists in pairs: round one merges list 0 with 1, 2 with 3 and so on, halving the count; repeat until one list remains. Each round touches every node once, and there are log k rounds. Merging two sorted lists is the standard two-pointer splice with a dummy head. This is merge sort's combine step applied log k times.
time O(N log k)space O(1) iterative / O(log k) recursive
Alternative approaches
- A min-heap of the current head of each list also gives O(N log k) with O(k) space and is the natural choice when lists arrive as a stream. Merging lists one by one into an accumulator is O(N · k).
Code it yourself
Solve in
Hints: