合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解题思路:
这是一个数组+链表组合题目,看到链表有序,我们首先想到链表合并子问题
1,这是合并两个有序链表的基础上的扩展
2,简单思路
将依次将第二个起都合并到第一个,复杂度O(k*n)
3,思路二,两两合并,复杂度O(logk*n)
4,注意长度可能是奇数,即使是偶数,两两合并后可能是奇数,需要特殊处理,否则数组越界问题很难处理,很容易死循环
5,扩展思路
用优先队列,每次取最小的元素合并,然后把当前链表下一个元素入队,直到队列为空
代码实现