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

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

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