给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
解题：
// 引入最小堆类,最小堆类构造参考https://blog.csdn.net/qq_43540219/article/details/108932367 /** * 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} */ // 因为我们比较的数据是ListNode,所以我们要修改一下最小堆类中的方法,改为比较.val,且确保存在被比较的节点 shiftUp(index) { if (index === 1) { return } const parentIndex = this.getParentIndex(index) if (this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) { this.swap(parentIndex, index); this.shiftUp(parentIndex) } } shiftDown(index) { const leftIndex = this.getLeftIndex(index) const rightIndex = this.getRightIndex(index) if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) { this.swap(leftIndex, index) this.shiftDown(leftIndex) } if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) { this.swap(rightIndex, index) this.shiftDown(rightIndex) } } // 且pop方法也要加上返回数据的逻辑 pop() { if (this.size() === 0) { return this.heap.shift() } const top = this.heap[0] this.heap[0] = this.heap.pop() // 将最后一位pop并且赋值给堆顶 this.shiftDown(0) return top } // 算法部分： /** * 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) // 新建一个链表头 let p = res const h = new MinHeap() lists.forEach(l => { if (l) { h.insert(l) } }) while (h.size()) { const n = h.pop() p.next = n p = p.next if (n.next) h.insert(n.next) } return res.next }