合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// 把所有元素存到一个数组中
let arr = []
for(let i=0; i< lists.length; i++) {
while(lists[i]) {
arr.push(lists[i].val)
lists[i] = lists[i].next
}
}
// 对数组进行排序
arr = arr.sort((a,b) => a-b)
// 重新组成一个链表
let res = new ListNode(0)
let node = res
arr.forEach(item => {
node.next = new ListNode(item)
node = node.next
})
return res.next
};