The problem
Given an array of k linked lists, each sorted from smallest to largest, merge them all into one sorted list and return it.
Examples
01
- Input
lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
- Output
[1, 1, 2, 3, 4, 4, 5, 6]
02
- Input
lists = []
- Output
[]
03
- Input
lists = [[]]
- Output
[]
Constraints
- 0 ≤ k ≤ 10⁴
- 0 ≤ each list’s length ≤ 500
- −10⁴ ≤ Node.val ≤ 10⁴
- The lists hold at most 10⁴ nodes in total.
The idea
As with two lists, the next node is always the smallest of the fronts — but now there are k fronts, and scanning them all each time costs k per node.
A min-heap is a tree kept so its smallest item is always on top, with insert and remove-smallest each costing log k. Put each list’s front in it. Repeatedly take the smallest, attach it to the answer, and push the next node from the same list. With N nodes in all, that is N log k.
- Time
- O(N log k) — N nodes, each through a heap of at most k
- Space
- O(k) — the heap
Solution · every language run against every case
class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: # A min-heap holds the front node of each list; the smallest front comes out first. heap = [(node.val, i, node) for i, node in enumerate(lists) if node] # i breaks ties heapify(heap) dummy = tail = ListNode() while heap: _, i, node = heappop(heap) tail.next = tail = node if node.next: heappush(heap, (node.next.val, i, node.next)) # that list's next front return dummy.next