You get lists, an array of k sorted linked lists.
Merge them all into one sorted list, and return its head.
Example 1:
Input: lists = [[2,5,9],[1,5],[3,4,10]] Output: [1,2,3,4,5,5,9,10] Explanation: The three lists are: 2 -> 5 -> 9 1 -> 5 3 -> 4 -> 10 The answer has all eight values in order. Both 5s stay.
Example 2:
Input: lists = [[-6,-1],[],[-6]] Output: [-6,-6,-1] Explanation: The empty list adds nothing. Both -6s stay, one from each list.
Example 3:
Input: lists = [[],[]] Output: [] Explanation: Both lists are empty. So the answer is None.
Constraints:
- 0 to 10,000 lists (
listsitself can be empty). - Each list has 0 to 500 nodes.
- All lists together have at most 10,000 nodes.
- Each value is from -10,000 to 10,000,000.
- Every list is in ascending order.
Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the total number of nodes across all lists and k is the number of lists.
Hints:
The brute force re-scans every list head each time. What data structure gives you the smallest of
k values in O(log k) instead of O(k)?
Use a min-heap seeded with the head of every non-empty list, ordered by the node's value.
Each iteration: extract the smallest node, append a copy of its value to the merged tail, and if it has a successor, push that successor onto the heap.
When the heap is empty, every list has been fully consumed.
The heap holds at most
k nodes at any time. Each of the n output nodes costs one extract and at most one insert, each O(log k) — Time Complexity is O(n log k).The heap itself uses
O(k) extra space.
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Free plan: 30 tutor messages. PRO is unlimited.
Saved
Ctrl + Enter to check
