解题步骤

  1. 构建一个最小堆，并依次把链表头插入堆中
  2. 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中
  3. 等堆元素全部弹出，合并工作就完成了

通过堆的方式实现

  • 时间复杂度： O (n log k)

  • 空间复杂度：O (k)

    1. function mergeKLists(lists) {
    2.   const res = new ListNode(0);
    3.   let p = res;
    4.   const h = new MinHeap();
    6.   lists.forEach((item) => {
    7.       if (item) h.insert(item);
    8.   });
    10.   while (h.size()) {
    11.       const n = h.pop();
    13.       p.next = n;
    14.       p = p.next;
    16.       if (n.next) h.insert(n.next);
    17.   }
    19.   return res.next;
    20. }

代码中第一个 ForEach 循环次数较少，我们忽略不计，而下面的 while 循环次数会相对多一些，循环了 n 次，所以时间复杂度 O (n) ，在 while 循环体内还有 pop 和 insert 操作，他们的时间复杂度是 log k ，k 代表链表的个数，所以整体的时间复杂度为 O (n log k)。

而空间复杂度是 O (k) ，因为我们主要使用了 MinHeap 作为中间变量。