Merge k Sorted Lists
HardLinked List · LinkedIn
You are given an array lists of k linked-list heads. Each linked list is sorted in non-decreasing order (some may be empty).
Merge all of them into a single linked list sorted in non-decreasing order and return its head. Keep every value, including duplicates. If there are no nodes at all (no lists, or only empty lists), return None.
Example 1
- Input:
- lists = [[2,6,9],[1,5],[3,4,10]]
- Output:
- [1,2,3,4,5,6,9,10]
- Explanation
- Repeatedly taking the smallest front value among the three lists gives 1, 2, 3, 4, 5, 6, 9, 10.
Example 2
- Input:
- lists = [[1,4],[],[1,1,3],[]]
- Output:
- [1,1,1,3,4]
- Explanation
- Empty lists contribute nothing. The three 1s come from two different lists and are all kept.
Example 3
- Input:
- lists = []
- Output:
- []
- Explanation
listsitself is empty, so the merged list is empty (None).
Constraints
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= Node.val <= 10^4- Each
lists[i]is sorted in non-decreasing order - The total number of nodes across all lists is at most
10^4