合并 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,扩展思路

用优先队列,每次取最小的元素合并,然后把当前链表下一个元素入队,直到队列为空

代码实现