LeetCode第二十三题-合并n个有序链表

时间:2022-11-21 19:16:15

Merge k Sorted Lists

问题简介:合并k个已排序的链表并将其作为一个排序链表返回.

举例:

输入:

[

1->4->5,

1->3->4,

2->6

]

输出: 1->1->2->3->4->4->5->6

链表结构:

LeetCode第二十三题-合并n个有序链表

解法一:

建立一个集合,遍历所有链表,将其元素添加到集合中,将集合通过数组的方式升序排序,将其添加到一个新的链表中并返回

LeetCode第二十三题-合并n个有序链表

复杂度分析:

时间复杂度:o(n2)外层遍历一遍数组内层遍历链表的元素,即双层遍历,还有一个单层遍历,所以结果近似于o(n2)

空间复杂度:o(n)定义了数组长度多的变量listNode,定义了集合长度的链表长度即o(n)

注:

1.将一个集合转为数组时,要注意这个数组的类型不能是基本类型

如int应写为Integer包装类型

LeetCode第二十三题-合并n个有序链表

小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海

LeetCode第二十三题-合并n个有序链表