No.23  合并 k 个有序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:[
  1->4->5,
  1->3->4,
  2->6
]输出: 1->1->2->3->4->4->5->6

这一题可以看作是前边第 21 题的升级版 ，小伙伴们可以温故一下之前类似的题目 ：

Leetcode打卡 | No.21 合并两个有序链表

这里是 k 个有序链表 ，小詹看到第一反应是直接递归使用前边合并两个有序链表的思路 ，对 ，完全没毛病的 。然后参考答案里是类似的 ，只不过合并的方式不一样 ，这里采取的是两两合并的方式 ，过程见下图 ：

这里可以很清晰的看懂思路 ，实现代码如下 ：

这种方式的结果大概是 beat 65% 左右 ，还有一种看起来比较复杂的办法 ，但是结果却很赞 。大体思路分为三步 ：

1. 创建一个列表
   
2. 将所有链表的元素值 append 进列表
   
3. 进行排序 ，之后再转换为链表结构
   

代码实现如下 ：

题目中要求描述下算法复杂度 ，这里以第二种 "三步曲" 的算法为例描述 ，另一方法读者自行尝试下哦 。

1. 时间复杂度 ，分为三步分别考虑 ，首先将所有链表节点值收集到列表中时间复杂度为 O(N) ；排序使用 python 的 sorted ，这里插一句 ，公号前期文章有 8 大排序算法的介绍 ，这步复杂度为 O(NlogN) ；第三步则是再创建链表 ，转换为目标结构为 O(N)
   
2. 空间复杂度 ，排序过程的空间复杂度取决于使用的算法 ，创建列表过程为 O(N)