分治
图解
复杂度
-
时间复杂度：
O(nlogk)，其中 k 为 lists 的长度，n 为所有链表的节点数之和； -
空间复杂度：
O(k)，堆中至多有 k 个元素，递归占用O(k)的栈空间；
代码实现
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
if (lists.length === 0) return null;
return mergeLists(lists, 0, lists.length - 1);
}
// 归并排序的思路 二分的思路
function mergeLists(lists: Array<ListNode | null>, start: number, end: number): ListNode {
if (start === end) {
return lists[start];
}
// 找到中间位置，将链表数组一分为二，分别进行排序
const mid = start + ((end - start) >> 1);
const leftList = mergeLists(lists, start, mid);
const rightList = mergeLists(lists, mid + 1, end);
// 将一分为二的链表合并在一起
return merge(leftList, rightList);
}
// 合并两个链表
function merge(head1:ListNode, head2:ListNode):ListNode {
let dmy = new ListNode(0);
let p = dmy;
while (head1 && head2) {
if (head1.val <= head2.val) {
p.next = head1;
head1 = head1.next;
} else {
p.next = head2;
head2 = head2.next;
}
p = p.next;
}
p.next = head1 ? head1 : head2;
return dmy.next;
}
小顶堆
复杂度
-
时间复杂度：
O(nlogk)，其中 k 为 lists 的长度，n 为所有链表的节点数之和； -
空间复杂度：
O(k)，堆中至多有 k 个元素；
代码实现
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
// 1. 将链表的值放到 nums 中
let nums = [];
for (const link of lists) {
let curr = link;
while (curr) {
nums.push(curr.val);
curr = curr.next;
}
}
// 2. 堆化，构建最小堆，时间复杂度是 0(N)
let minHeap = new Heap(nums, nums.length, (a, b) => a > b);
// 3. 最小堆依次出队，构建链表
let dummy = new ListNode(0, null);
let cur = dummy;
while (!minHeap.isEmpty()) { // 循环直到堆为空
let num = minHeap.poll();
console.log(num);
cur.next = new ListNode(num, null); // 合并到新链表中
cur = cur.next; // 准备合并下一个节点
}
return dummy.next;
};
class Heap {
private _data: number[];
private _capacity: number;
private compare: (a: number, b: number) => boolean;
constructor(nums: number[], capacity: number, compare = (a, b) => a < b) {
this._data = [0, ...nums]; // 数据从 1 开始存储
this._capacity = capacity;
this.compare = compare || ((a, b) => a > b);
// 从 1 开始编号的堆最后一个非叶子结点的下标是 size/2 （画图就可以观察出来）
for (let index = this._data.length >> 1; index >= 1; index--) {
this.siftDown(index);
}
}
// 当前最大堆中真正存储的元素的个数
get size() {
return this._data.length - 1;
}
isEmpty() {
return this.size === 0;
}
/**
* 返回队首元素
* @returns
*/
peek() {
if (this.isEmpty()) {
return;
}
// 下标 0 不存元素
return this._data[1];
}
/**
* 入队
* @param item
*/
offer(item: number) {
if (this.size + 1 > this._capacity) {
return;
}
// 把新添加的元素放在数组的最后一位
this._data.push(item);
// 将 入队 的元素上移到合适的位置
this.siftUp(this.size);
}
/**
* 元素上浮
* @param k 索引
*/
siftUp(k: number) {
// 有下标就要考虑索引越界的情况，已经在下标 1 的位置，就没有必要上移了
while (k > 1 && this.compare(this._data[this.parent(k)], this._data[k])) {
this.swap(this.parent(k), k);
k = this.parent(k);
}
}
/**
* 元素上浮，与 siftUp() 方法等价
* @param k 索引
*/
shiftUp(k: number) {
// 编写方式等价于「插入排序」的优化，先暂存，再逐个移动，最后空出位置把先前暂存元素放进去
const temp = this._data[k];
while (k > 1) {
if (this.compare(this._data[this.parent(k)], temp)) {
this._data[k] = this._data[this.parent(k)];
k /= 2;
} else {
break;
}
}
this._data[k] = temp;
}
/**
* 堆顶元素出队
* @returns
*/
poll() {
if (this.size == 0) {
return;
}
const res = this.peek(); // 队首元素
// 把最后一个元素的值赋值到二叉堆的根结点
this.replace(this._data.pop());
return res;
}
/**
* 元素下沉
* @param k 索引
*/
siftDown(k: number) {
// 只要它有孩子，注意这里使用等于号，是因为真正存数据的下标从 1 开始
while (this.leftChild(k) <= this.size) {
// 1. 拿到左右节点的最大值
let leftChildInx = this.leftChild(k);
let rightChildInx = this.rightChild(k);
if (rightChildInx <= this.size && this.compare(this._data[leftChildInx], this._data[rightChildInx])) {
leftChildInx = rightChildInx;
}
// 2. k 满足大顶堆，什么都不做
if (this.compare(this._data[leftChildInx], this._data[k])) {
break;
}
// 3. 交换位置后，继续下沉操作
this.swap(k, leftChildInx);
k = leftChildInx; // 更新位置
}
}
/**
* 元素下沉，与 siftDown() 方法等价
* @param k 索引
*/
shiftDown(k: number) {
// 编写方式等价于「插入排序」的优化，先暂存，再逐个移动，最后空出位置把先前暂存元素放进去
let temp = this._data[k];
while (this.leftChild(k) <= this.size) {
// 1. 拿到左右节点的最大值
let leftChildInx = this.leftChild(k);
let rightChildInx = this.rightChild(k);
if (rightChildInx <= this.size && this.compare(this._data[leftChildInx], this._data[rightChildInx])) {
leftChildInx = rightChildInx;
}
// 2. k 满足大顶堆，什么都不做
if (this.compare(this._data[leftChildInx], temp)) {
break;
}
// 3. 依次后移，继续下沉操作
this._data[k] = this._data[leftChildInx];
k = leftChildInx; // 更新位置
}
this._data[k] = temp;
}
/**
* 指定元素替换到队首
* @param item
*/
replace(item: number) {
if (this.isEmpty()) {
return;
}
this._data[1] = item;
this.siftDown(1);
}
/**
* 获取左边孩子节点索引
* @param k
* @returns
*/
leftChild(k: number) {
return k * 2;
}
/**
* 获取右边孩子节点索引
* @param k
* @returns
*/
rightChild(k: number) {
return k * 2 + 1;
}
/**
* 获取父节点索引
* @param k
* @returns
*/
parent(k: number) {
return k >> 1;
}
/**
* 交换位置
* @param i 索引
* @param j 索引
*/
swap(i: number, j: number) {
[this._data[i], this._data[j]] = [this._data[j], this._data[i]];
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 21. 合并两个有序链表
上一篇
评论
