23. 合并 K 个升序链表

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 <= 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⁴.

Solution #

Language: Go

将每个链表的头部记录在 set 中，并做好 head 的值与 链表 index 的映射。每次从 set 取出链表中最小的头部 value，去 map 中查询出等值的链表 index（使用 queue 保存），依次将链表元素取出。边界是当 set 中不存在元素时所有链表取完。

IOI