topic23

合并k个有序链表

1. 题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

2. 示例

示例1

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例2

输入：lists = []
输出：[]

示例3

输入：lists = [[]]
输出：[]

3. 解题

采用收集法，类似桶排序，初始化桶为若干个链表数组，数组的每个元素都是一个链表。 将各个数组中的链表元素依次收集到对应的数组元素中，收集完成后再进行合并。