Merge k Sorted Lists
Hard · Linked Lists · Linked List · Divide and Conquer · Heap (Priority Queue) · Merge Sort
Problem
You are given lists, a Python list of k singly linked lists. Each one is sorted in ascending order (repeated values allowed), and any of them may be empty — an empty list is a head of None. Merge them all into one sorted linked list and return its head.
lists itself may be empty (k = 0). Then there is nothing to merge: return None.
The tests build every list with from_list([...]) and read your answer back with to_list(), both already defined. There can be up to 10,000 lists holding 10,000 nodes between them, so the approach you pick matters: folding the lists into the result one at a time walks the growing result again for every list, and with thousands of short lists that is tens of millions of steps.
Examples
Input: lists = [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6] Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Every node of the three lists, in ascending order. The two 1s and the two 4s come from different lists.
Input: lists = [None, 2 -> 3, None, 1] Output: 1 -> 2 -> 3
The empty lists add nothing. The one-node list holds the smallest value, so its node comes first.
Constraints
- 0 <= k <= 10^4, where k = len(lists)
- 0 <= number of nodes in each list <= 500
- at most 10^4 nodes in all the lists together
- -10^4 <= Node.val <= 10^4
- each list is sorted in non-decreasing order
Approaches
- Merge the lists in one after another — time O(k · N), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
