题目:
难度:Hard
相关话题:堆
、链表
、分治算法
合并k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
思路:
好几种方法能解决,
直接排序,将每一个node.val
添加到数组,然后排序后重新生成链表。
优先队列,将每一个node
加入Priority Queue
,然后再从小到大导出即可。
归并排序(见代码)。
多指针(比较慢),每一次都找出当前每一个list[i]
中的最小值,找到的那个节点执行list[i]=list[i].next
。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
return divid(lists,0,lists.length-1)
function merge2Lists(list1,list2){
if(list1==null)return list2
if(list2==null)return list1
if(list1.val<list2.val){
list1.next=merge2Lists(list1.next,list2);
return list1;
}else{
list2.next=merge2Lists(list1,list2.next);
return list2;
}
}
function divid(lists,left,right){
if(left===right) return lists[left];
if(left>right) return null
let mid=Math.floor((left+right)/2)
let list1=divid(lists,left,mid)
let list2=divid(lists,mid+1,right)
return merge2Lists(list1,list2)
}
};