Merge k Sorted Lists
Hard· divide and conquer· merge
Problem
You get an array of k linked lists, each sorted ascending. Combine them into a single sorted linked list and return its head.
Examples
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Input: lists = [[]]
Output: []
Constraints
- • 0 <= k <= 10^4
- • Total nodes N <= 10^4
- • Each list is sorted ascending
Hints & approach
Hint 1
Merging the lists one after another into a growing result costs O(kN).
Hint 2
Merge them in pairs, like the merge step of merge sort.
Hint 3
Alternatively, keep the current head of every list in a min-heap.
Approachtry the hints first
Divide and conquer: merge list 0 with 1, 2 with 3, and so on, halving the number of lists each round using the two-list merge. After log k rounds one list remains, and every node took part in log k merges. The min-heap alternative pushes each list's head, then repeatedly pops the smallest node, appends it, and pushes that node's successor; it has the same bound.
Time O(N log k) · Space O(1) for pairwise merging, O(k) with a heap