LeetCode：23. 合并K个排序链表

使用最小堆

/**
 * JavaScript 实现：最小堆类
 * 插入
 * 删除
 * 返回堆头
 * 返回堆长
 */

class MinHeap {
    constructor() {
        this.heap = []
    }

    swap(i1, i2) {
        // 交换两个值
        const temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }

    getParentIndex(i) {
        // 获取父元素的索引值 (index-1)/2
        // 类似 Math.floor((index-1/2))
        return (i - 1) >> 1
    }

    getLeftIndex(i) {
        // 获取左元素的索引值 i*2+1
        // 类似 Math.floor((index-1/2))
        return i * 2 + 1
    }

    getRightIndex(i) {
        // 获取右元素的索引值 i*2+2
        // 类似 Math.floor((index-1/2))
        return i * 2 + 2
    }

    shiftUp(index) {
        if (index === 0) return;

        const parentIndex = this.getParentIndex(index)

        // 较小的值 上移
        if (this.heap[parentIndex] && this.heap[index].val < this.heap[parentIndex].val) {
            this.swap(index, parentIndex)
            this.shiftUp(parentIndex)
        }
    }

    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index)
        const rightIndex = this.getRightIndex(index)

        // 较大的值 下移
        if (this.heap[leftIndex] && this.heap[index].val > this.heap[leftIndex].val) {
            this.swap(index, leftIndex)
            this.shiftDown(leftIndex)
        }

        // 较大的值 下移
        if (this.heap[rightIndex] && this.heap[index].val > this.heap[rightIndex].val) {
            this.swap(index, rightIndex)
            this.shiftDown(rightIndex)
        }
    }

    insert(val) {
        // 插入新值
        this.heap.push(val)
        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
    }
    peek() {
        // 返回堆顶
        return this.heap[0]
    }

    size() {
        // 返回堆容量
        return this.heap.length
    }
}


/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    const res = new ListNode(0)
    const h = new MinHeap()
    let p = res
    
    // 推到堆中得到 MinHeap { heap: [ [1,4,5], [1,3,4], [2,6] ] }
    lists.forEach(l=>{        
        if(l) h.insert(l)
    })

    while(h.size()){
        // 分别弹出 [1,4,5], [1,3,4], [2,6] 链表
        const n = h.pop()
        p.next = n // {val:1} 这种结构
        p = p.next
        if(n.next) h.insert(n.next)
    }

    return res.next
};

发现使用数组排序也挺好的

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    // 发现用数组排序也行
    let list = []
    for(let i=0;i<lists.length;i++){
        let node = lists[i]
        while(node){
            list.push(node.val) 
            node = node.next 
        }
    }

    list = list.sort((a,b)=>a-b)

    let res = new ListNode(0)
    let p = res
    list.forEach(n=>{
        p.next = new ListNode(n)
        p = p.next
    })

    return res.next
};