23. 合并 K 个升序链表

题目

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

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

题解

构建最小堆

/**
 * 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 fakeHead = new ListNode(0);
  let node = fakeHead;
  lists = lists.filter(l => l);
  buildMinHeap(lists);

  while (lists.length) {
    node.next = lists.shift();
    node = node.next;

    if (node.next) {
      lists.push(node.next);
    }
    buildMinHeap(lists);
  }
  return fakeHead.next;
};

function buildMinHeap(arr) {
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    minHeapify(arr, i, arr.length);
  }
}

function minHeapify(arr, i, heapSize) {
  let l = 2 * i + 1;
  let r = l + 1;

  let min = i;
  if (l < heapSize && arr[min].val > arr[l].val) {
    min = l;
  }
  if (r < heapSize && arr[min].val > arr[r].val) {
    min = r;
  }

  if (min != i) {
    let t = arr[i];
    arr[i] = arr[min];
    arr[min] = t;
    minHeapify(arr, min, heapSize);
  }
}