原题地址：合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
准备工作
定义链表结点：
function ListNode(val) {
this.val = val;
this.next = null;
}
数组转链表，方便测试数据的输入：
function arrayToList(array) {
let node = null;
for (let i = array.length - 1; i >= 0; i --) {
let newNode = new ListNode(array[i]);
newNode.next = node;
node = newNode;
}
return node;
}
链表转字符串，方便测试结果的显示：
function listToString(node) {
return node ? `${node.val}${node.next ? ` -> ${listToString(node.next)}` : '' }` : null;
}
暴力法
直接将所有的链表元素组合成一个数组，然后对数组进行排序，再将排过序的数组转换成链表：
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
const mergeKLists1 = function(lists) {
let array = [];
// 链表转数组
for (let node of lists) {
while (node) {
array.push(node.val);
node = node.next;
}
}
array.sort((a, b) => a - b);
let preHead = new ListNode(null); // 定义一个头结点之前的结点，方便最后的输出
let tail = preHead;
// 数组再转链表
for (let item of array) {
tail.next = new ListNode(item);
tail = tail.next;
}
return preHead.next;
};
测试：
let start = new Date();
const test = mergeKLists1;
console.log(listToString(test([
arrayToList([1, 4, 5]),
arrayToList([1, 3, 4]),
arrayToList([2, 6]),
]))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 设链表所有的元素之和为n，则链表转数组和数组转链表都需要遍历所有元素，时间复杂度均为O(n)，而数组排序的时间复杂度为O(nlogn)，所以总的时间复杂度为O(nlogn)
空间复杂度： 生成新的链表，空间复杂度为O(n)
转换成双链表的合并
我们之前做过 合并两个有序链表，现在要合并k个有序链表，只需要将这k个有序链表两两依次合并即可：
/**
* 合并两个链表
* @param l1 链表一
* @param l2 链表二
* @returns {ListNode} 合并后的链表
*/
const mergeTwoLists = function(l1, l2) {
let preHead = new ListNode(null); // 定义一个头结点之前的结点，方便最后的输出
let tail = preHead; // 新链表的尾结点
while (l1 && l2) {
// 两链表都不为空时，尾结点的next指向值较小的结点，同时将该链表的指针后移
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
// 尾结点后移
tail = tail.next;
}
// 尾结点指向剩下不为空的结点
tail.next = l1 || l2;
return preHead.next;
};
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
const mergeKLists2 = function(lists) {
if (lists.length === 0) {
return null;
}
let result = lists[0];
// 依次将之前合并得到的链表与新链表合并
for (let i = 1; i < lists.length; i++) {
result = mergeTwoLists(result, lists[i]);
}
return result;
};
测试：
let start = new Date();
const test = mergeKLists2;
console.log(listToString(test([
arrayToList([1, 4, 5]),
arrayToList([1, 3, 4]),
arrayToList([2, 6]),
]))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
console.log(new Date().getTime() - start.getTime()); // 6
时间复杂度： 每次合并两个链表时就需要遍历之前合并过的链表与新的要合并的链表，所以总的时间复杂度为O(kn)，k为链表数组的长度，n为最终合并后链表的长度
空间复杂度： 只需要常数个额外空间，空间复杂度为O(1)
利用分治优化双链表的合并
我们将该题转化为双链表的合并时，合并过的链表每次都需要被重复遍历，我们可以利用分治来优化该过程。将需要合并的链表两两分组，每次进行组内合并，合并过的链表再进行两两分组，依此类推：
/**
* 合并两个链表
* @param l1 链表一
* @param l2 链表二
* @returns {ListNode} 合并后的链表
*/
const mergeTwoLists = function(l1, l2) {
let preHead = new ListNode(null); // 定义一个头结点之前的结点，方便最后的输出
let tail = preHead; // 新链表的尾结点
while (l1 && l2) {
// 两链表都不为空时，尾结点的next指向值较小的结点，同时将该链表的指针后移
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
// 尾结点后移
tail = tail.next;
}
// 尾结点指向剩下不为空的结点
tail.next = l1 || l2;
return preHead.next;
};
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
const mergeKLists3 = function(lists) {
if (lists.length === 0) {
return null;
}
// 步长每次乘以2
for (let i = 1; i < lists.length; i *= 2) {
// 分组合并
for (let j = 0; j < lists.length; j += i * 2) {
lists[j] = mergeTwoLists(lists[j], lists[j + i]);
}
}
return lists[0];
};
测试：
let start = new Date();
const test = mergeKLists3;
console.log(listToString(test([
arrayToList([1, 4, 5]),
arrayToList([1, 3, 4]),
arrayToList([2, 6]),
]))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 只需要$log_2k$次合并，所以总的时间复杂度为O(nlogk)
空间复杂度： 只需要常数个额外空间，空间复杂度为O(1)
逐一比较
我们可以逐一比较每个链表头结点的大小，选出最小的头结点加入到新链表中，并将该链表指针后移，最终即可得到合并过的链表，整体思路与两个链表的合并是一样的：
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
const mergeKLists4 = function(lists) {
if (lists.length === 0) {
return null;
}
let preHead = new ListNode(null); // 定义一个头结点之前的结点，方便最后的输出
let tail = preHead; // 新链表的尾结点
let [minNode, index] = [null, null]; // 记录最小的头结点及它的数组中的索引
while (1) {
minNode = null;
// 找出最小的头结点及其索引
for (let i = 0; i < lists.length; i++) {
if (lists[i] && (!minNode || lists[i].val < minNode.val)) {
minNode = lists[i];
index = i;
}
}
// 如果没有找到，证明所有的数组都已经为空，合并已完成
if (!minNode) {
break;
}
// 头结点最小的链表指针后移
lists[index] = lists[index].next;
tail.next = minNode; // 新链表尾结点指向找到的最小头结点
tail = tail.next; // 新链表尾结点后移
}
return preHead.next;
};
测试：
let start = new Date();
const test = mergeKLists4;
console.log(listToString(test([
arrayToList([1, 4, 5]),
arrayToList([1, 3, 4]),
arrayToList([2, 6]),
]))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 合并每个结点时都需要找出当前数组中最小的头结点，要进行k次比较，所以总的时间复杂度为O(kn)
空间复杂度： 只需要常数个额外空间，空间复杂度为O(1)
利用堆优化逐一比较的过程
我们合并每个结点时的比较是为了找出最小的头结点，而最小堆则有堆顶元素最小这个特性，所以我们可以利用堆来优化这一比较过程：
/**
* 最小堆
*/
class MinHeap {
constructor() {
this.items = [];
}
/**
* 将指定位置的元素上移到它应该在的位置
* @param index 需要上移的元素位置
*/
shiftUp(index) {
let parent = Math.floor((index - 1) / 2);
while (index > 0 && this.items[index].val < this.items[parent].val) {
[this.items[index], this.items[parent]] = [this.items[parent],this.items[index]];
index = parent;
parent = Math.floor((index - 1) / 2);
}
}
/**
* 将指定位置的元素下移到它应该在的位置
* @param index 需要下移的元素位置
*/
shiftUpDown(index) {
// 左右子结点
let [left, right] = [2 * index + 1, 2 * index + 2];
// 还有下一层才能下移
while (left < this.items.length) {
if (right >= this.items.length || this.items[left].val < this.items[right].val) {
if (this.items[index].val > this.items[left].val) {
[this.items[index], this.items[left]] = [this.items[left], this.items[index]];
index = left;
[left, right] = [2 * index + 1, 2 * index + 2];
} else {
break;
}
} else {
if (this.items[index].val > this.items[right].val) {
[this.items[index], this.items[right]] = [this.items[right], this.items[index]];
index = right;
[left, right] = [2 * index + 1, 2 * index + 2];
} else {
break;
}
}
}
}
// 插入元素
insert(item) {
this.items.push(item);
this.shiftUp(this.items.length - 1);
}
// 弹出堆顶元素
remove() {
if (this.isEmpty()) {
return null;
}
[this.items[0], this.items[this.items.length - 1]] = [this.items[this.items.length - 1], this.items[0]];
const item = this.items.pop();
this.shiftUpDown(0);
return item;
}
// 判断是否为空
isEmpty() {
return this.items.length === 0;
}
}
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
const mergeKLists6 = function(lists) {
if (lists.length === 0) {
return null;
}
let preHead = new ListNode(null); // 定义一个头结点之前的结点，方便最后的输出
let tail = preHead; // 新链表的尾结点
// 构建初始堆
let heap = new MinHeap();
for (let i = 0; i < lists.length; i++) {
if (lists[i]) {
heap.insert(lists[i]);
lists[i] = lists[i].next;
}
}
while (!heap.isEmpty()) {
// 弹出堆顶元素
tail.next = heap.remove();
// 如果堆顶元素的next不为空，则将该元素插入堆
if (tail.next.next) {
heap.insert(tail.next.next);
}
tail = tail.next;
}
return preHead.next;
};
测试：
let start = new Date();
const test = mergeKLists6;
console.log(listToString(test([
arrayToList([1, 4, 5]),
arrayToList([1, 3, 4]),
arrayToList([2, 6]),
]))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 最小堆的元素数量最多不超过k，插入和删除的时间复杂度都为O(logk)， 所以总的时间复杂度为O(nlogk)
空间复杂度： 需要一个最小堆，元素数量不超过k，空间复杂度为O(k)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 30,2019