Description #
Difficulty: 困难
Related Topics: 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 <= 104
0 <= lists[i].length <= 500
- -104 <= lists[i][j] <= 104
lists[i]
is sorted in ascending order.- The sum of
lists[i].length
will not exceed 104.
Solution #
Language: Go
将每个链表的头部记录在 set 中,并做好 head 的值与 链表 index 的映射。每次从 set 取出链表中最小的头部 value,去 map 中查询出等值的链表 index(使用 queue 保存),依次将链表元素取出。边界是当 set 中不存在元素时所有链表取完。
IOI