Merge k Sorted Lists
问题简介:合并k个已排序的链表并将其作为一个排序链表返回.
举例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
链表结构:
解法一:
建立一个集合,遍历所有链表,将其元素添加到集合中,将集合通过数组的方式升序排序,将其添加到一个新的链表中并返回
复杂度分析:
时间复杂度:o(n2)外层遍历一遍数组内层遍历链表的元素,即双层遍历,还有一个单层遍历,所以结果近似于o(n2)
空间复杂度:o(n)定义了数组长度多的变量listNode,定义了集合长度的链表长度即o(n)
注:
1.将一个集合转为数组时,要注意这个数组的类型不能是基本类型
如int应写为Integer包装类型
小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海