Merge K Sorted Linked Lists
Merge k independently sorted linked lists into a single sorted linked list.
You are given an array of k singly-linked lists, where each list is already sorted in ascending order.
Merge all of the lists into one sorted linked list and return its values in order.
Any of the input lists may be empty, and the array of lists itself may be empty.
Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Example 2
Input: lists = []
Output: []
Explanation: With no lists to merge, the result is an empty list.
Example 3
Input: lists = [[]]
Output: []
Explanation: A single empty list merges to an empty list.
Constraints
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- Each individual list is already sorted in ascending order.
- The total number of nodes across all lists does not exceed 10^4.
Follow-up
Can you do better than merging the lists one at a time (O(k*n) overall)? Consider a divide-and-conquer merge or a min-heap over the k current front nodes to reach O(n log k).
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.