You are given an array of k linked lists, each already sorted in ascending order. Merge all of them into one sorted linked list and return its head. The array may be empty, and some of the lists may be empty.
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- Total number of nodes N <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force collects every value, sorts them and builds a new list: O(N log N) time and O(N) space. Merging the lists one by one into a growing result is O(N * k), because early nodes get re-walked again and again. The key insight is that the next answer node is always one of the k current heads, and a min-heap of size k gives us the smallest head in O(log k). Each of the N nodes goes into and out of the heap once, so the total is O(N log k). Divide and conquer (merging pairs of lists, like merge sort) reaches the same bound.
Algorithm
- Push the head of every non-empty list into a min-heap ordered by node value.
- Create a dummy node and a
tailpointer. - While the heap is not empty, pop the smallest node and attach it after
tail. - If the popped node has a
next, push thatnextinto the heap. - Return
dummy.next.
O(N log k), N = total nodesSpace: O(k) for the heap(val, node) crashes when two values are equal because nodes cannot be compared; add a unique counter as a tie breaker: (val, i, node). Be ready to explain the divide and conquer alternative with the same complexity.class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: heap = [] for i, head in enumerate(lists): if head: # i breaks ties so nodes are never compared directly heapq.heappush(heap, (head.val, i, head)) dummy = ListNode(0) tail = dummy while heap: _, i, node = heapq.heappop(heap) # smallest current head tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next