共计 1451 个字符，预计需要花费 4 分钟才能阅读完成。
合并 K 个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
1. 暴力破解法
此解法过于暴力，请谨慎使用
原理就是把所有的节点拆解，排序，再从新组合成一个列表，道理容易理解
时间复杂度为 O(nlogn)
2. 枚举法
此解法的主要思路为遍历所有列表的头部值，把最小的一个推入到当前结果队列里
具体解法为
var isOver = function (lists) {
let r = true
lists.map(val => {
if (val) {
r = false
return r
}
})
return r
}
var minNode = function (lists) {
let val = null
let j
for (var i = 0; i < lists.length; i++) {
if (lists[i]) {
if (val === null) {
val = lists[i].val
}
// console.log(lists[i].val, val)
if (lists[i].val <= val) {
val = lists[i].val
j = i
}
}
}
console.log(j)
let m = new ListNode(lists[j].val)
lists[j] = lists[j].next
return m
}
var mergeKLists = function(lists) {
if (lists.length === 0) return ”
let result = null
while (!isOver(lists)) {
if (!result) {
result = minNode(lists)
} else {
let z = result
while (z.next) {
z = z.next
}
z.next = minNode(lists)
}
}
return result
};
最极端的情况下我们每次获取元素都需要遍历 k 个链表，那么复杂度就是 O(kn),k 值复杂度越高。不一定比方法 - 更快
3. 分治法
我们只需要把相邻列表进行合并，这样的话我们只需要进行 logN 次操作就可以把列表归并成一个有序列表
递归深度一共是 logk，每一层的递归操作次数都是 n 次，n 是所有元素的个数。那么总的复杂度就是 O(nlogk)
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
if(lists.length == 0) return null;
var k = lists.length;
while(k > 1){
for (let i = 0; i < ~~(k / 2); i++) {
lists[i] = mergeTwoLists(lists[i], lists[i + ~~((k + 1) / 2)]);
}
k = ~~((k + 1) / 2);
}
return lists[0];
};
var mergeTwoLists = function (l1, l2) {
if (l1 == null) return l2
if (l2 == null) return l1
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
提交