输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
输入:lists = []
输出:[]
输入:lists = [[]]
输出:[]
1 )使用堆
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
class MinHeap {
heap: Array<ListNode | null> = [];
// 交换节点位置
swap(i, j) {
if (i === j) return;
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
// 获得父节点
getParentIndex(i) {
return (i - 1) >> 1;
}
// 获取左子节点
getLeftIndex(i) {
return (i << 1) + 1; // 极客写法
}
// 获取右子节点
getRightIndex(i) {
return (i << 1) + 2;
}
// 上移操作封装 是个递归
shiftUp(i) {
// 如果到了堆顶元素,index是0,则不要再上移了
if(!i) return;
// 获得父节点下标: pi
const pi = this.getParentIndex(i);
// 开始做比较
if(this.heap[pi]?.val > this.heap[i].val) {
// 实现交换
this.swap(pi, i);
// 继续尝试上移操作
this.shiftUp(pi);
}
}
// 下移操作
shiftDown(i) {
// 如果到了堆尾元素,则不要再下移了
if(i >= this.heap.length - 1) return;
const li = this.getLeftIndex(i); // 左孩子索引
const ri = this.getRightIndex(i); // 右孩子索引
// 左孩子节点的值 < 当前节点的值 注意:左右对比中,this.heap[i]不能用变量替代,因为内部有swap和shiftDown,使用变量会导致bug
if(this.heap[li]?.val < this.heap[i].val) {
this.swap(li, i);
this.shiftDown(li);
}
// 同样,对右孩子节点的值 < 当前节点的值
if(this.heap[ri]?.val < this.heap[i].val) {
this.swap(ri, i);
this.shiftDown(ri);
}
}
// 插入
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
// 删除堆顶
pop() {
if(this.size() === 1) return this.heap.shift();
const top = this.heap[0];
// 变相删除堆顶, 堆尾元素移动到堆顶
this.heap[0] = this.heap.pop(); // 删除数组的最后一个元素并返回,返回值赋值给堆顶元素
// 执行堆顶下移操作,维持堆的有序性
this.shiftDown(0);
return top;
}
// 获取堆顶
peak() {
return this.heap[0];
}
// 获取堆的大小
size() {
return this.heap.length;
}
}
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
const res = new ListNode(0);
let p = res;
const h = new MinHeap();
// 通过输入来构建堆结构
// 三个链表,堆中存入的是三个链表的头
lists.forEach(l => {
l && h.insert(l); // l是个链表,其实用的是链表头表示,也就是链表的第一个元素
})
// while循环,每一轮pk的都是堆内的元素
// 谁出队,就把谁的下一个入堆,逐个比较
// 最终堆空了,比较全部结束
while(h.size()) {
const n = h.pop(); // 弹出堆顶元素,最小值
p.next = n; // 将堆顶元素挂载在新链表上
p = p.next; // 链表指针移位,为下次连接做准备
n.next && h.insert(n.next) // 将弹出的堆顶元素的下一个元素入堆,进行重新构建堆结构
}
return res.next; // 返回的是next, 因为其第一个节点是我们new出来,用于连接的,所以不包含第一个节点
}