23. [✔][H]合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：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

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

---

题解：

/*
 * @lc app=leetcode.cn id=23 lang=typescript
 *
 * [23] 合并K个升序链表
 */

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)
    }
}

// @lc code=start
/**
 * 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)
 *     }
 * }
 */
// @ts-ignore
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if (lists.length === 0) {
        return null;
    }

    // @ts-ignore
    let dummy = new ListNode(-1);

    let p = dummy;


    class Heap {
        data: ListNode[];
        comparator: Function;

        constructor(comparator = (a: ListNode, b: ListNode) => a.val < b.val, data = []) {
            this.comparator = comparator;
            this.data = data;
            this.heapify();
        }

        // 堆化
        heapify() {
            // 1个或者0个，没必要堆化了
            if (this.size() < 2) return;

            // 这为啥从中间开始？值堆化一半就够了？
            for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
                this.bubbleDown(i);

            }
        }

        // 元素往上走
        bubbleUp(index: number) {
            while (index > 0) {
                const pIndex = (index - 1) >> 1; //注意：父节点位置，很有意思的一步

                // 往上走，所以要比较他和他爹谁大
                if (this.comparator(this.data[index], this.data[pIndex])) {
                    this.swap(index, pIndex);//跟他爹换换位置
                    index = pIndex;
                } else {
                    break;
                }
            }
        }

        // 元素往下沉
        bubbleDown(index: number) {
            const lastIndex = this.size() - 1;

            while (true) {
                const leftIndex = index * 2 + 1;//左子节点index
                const rightIndex = index * 2 + 2;// 右子节点index
                let findIndex = index; //当前bubbleDown节点的位置

                // 左节点跟根节点对比，选择符合条件的
                if (leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex])) {
                    findIndex = leftIndex;
                }

                // 右节点跟根节点对比，选择符合条件的上去
                if (rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex])) {
                    findIndex = rightIndex;
                }

                // 说明有变化，做了交换
                if (index !== findIndex) {
                    this.swap(index, findIndex);
                    index = findIndex;
                } else {
                    break;
                }
            }
        }

        // 交换两个元素位置
        swap(i: number, j: number) {
            [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
        }

        // 返回堆顶元素
        peek() {
            return this.size() >= 0 ? this.data[0] : null;
        }

        // 往堆里面添加一个值
        offer(value: ListNode) {
            this.data.push(value);//添加一个元素，相当于放到了最右下角的子节点,index为数组最后一个
            this.bubbleUp(this.size() - 1);
        }

        // 移除堆顶元素，重新构建堆，返回删除的元素
        poll() {
            if (this.size() === 0) {
                return null;
            }
            // 把第一个扔到最后面去，然后把最后一个扔到第一个，然后让第1个往下沉。
            this.swap(0, this.size() - 1);
            let result = this.data.pop()!;
            this.bubbleDown(0);
            return result;
        }

        // 堆的大小
        size() {
            return this.data.length;
        }
    }

    let heap = new Heap((a: ListNode, b: ListNode) => (a.val < b.val), [])

    for (const node of lists) {
        if (node !== null) {
            heap.offer(node);
        }
    }

    while (heap.size() > 0) {
        let node = heap.poll();
        p.next = node;

        // [[1,4,5],[1,3,4],[2,6]]
        // 当前堆中起始只存了1/1/2三个节点，当1被使用了以后，就要把1的下一个节点4放进去，构成4/1/2的堆，重新构建,也就是说堆只放了每个链表的头节点，当头节点被作为堆顶pop出来之后，就要把当前链表的下一个节点放进去
        if (node?.next !== null) {
            heap.offer(node?.next!);
        }
        p = p.next!;
    }

    return dummy.next;

};
// @lc code=end