Merge K Sorted Lists
Hard
Linked List
Divide and Conquer
Heap (Priority Queue)
Merge Sort
You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order. *Merge all the linked-lists into one sorted linked-list and return it.*
Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are: [1,4,5], [1,3,4], [2,6]. Merging them into one sorted list: 1->1->2->3->4->4->5->6
Example 2
Input: lists = []
Output: []
Example 3
Input: lists = [[]]
Output: []

Constraints

  • •k == lists.length
  • •0 <= k <= 10⁴
  • •0 <= lists[i].length <= 500
  • •-10⁴ <= lists[i][j] <= 10⁴
  • •lists[i] is sorted in ascending order.
  • •The sum of lists[i].length will not exceed 10⁴.
Time Complexity
O(N log k)
Space Complexity
O(k)
14
Case 1
Input: [[1,4,5],[1,3,4],[2,6]]
Expected: [1,1,2,3,4,4,5,6]
Case 2
Input: []
Expected: []
Case 3
Input: [[]]
Expected: []