23. 合并K个升序链表

题设¶

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

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

输入：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

解法一：暴力法¶

创建一个新的空链表，作为合并结果链表
遍历链表头，选取最小值节点
从原链表中删除，加入新的链表
假设 k 个链表，每个平均链表长度为 n，时间复杂度 O(nk * 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), p = fakeHead;
  const k = lists.length;

  let isEmpty = false;
  while (!isEmpty) {
    isEmpty = true;
    let min = 0;
    for(let i = 0; i < k; i++) {
      if (lists[i]) {
        isEmpty = false;
        if (!lists[min] || lists[min].val > lists[i].val) {
          min = i;
        }
      }
    }

    if (lists[min]) {
      p.next = lists[min];
      p = p.next;
      lists[min] = lists[min].next;
    }
  }

  return fakeHead.next;
};

解法二：最小堆¶

对 k 个链表头创建一个大小为 k 的最小堆
每次取出最小数，所需时间 O(log(k))
整体时间复杂度 O(nk * log(k))
空间复杂度 O(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) {
  // 1. 利用一个空链表头，方便插入节点
  let fakeHead = new ListNode(0), p = fakeHead;
  const k = lists.length;

  // 2. 定义一个最小堆来保存 k 个链表节点
  const queue = new PriorityQueue((a, b) => {
    return a.val - b.val;
  });

  // 3. 将 k 个链表头放入最小堆中
  for(let i = 0; i < k; i++) {
    if (lists[i]) {
      queue.enqueue(lists[i]);
    }
  }

  while(queue.size() > 0) {
    // 4. 从最小堆中取出当前最小值，插入结果链表中
    let node = queue.dequeue();

    p.next = node;
    p = p.next;

    // 5. 如果发现该节点还有后续节点，将其加入最小堆
    if (node.next) {
      queue.enqueue(node.next);
    }
  } 

  return fakeHead.next;
}

解法三：分治理法¶

利用归并排序思想，将列表两两归并
时间复杂度同样 O(nk * log(k))
空间复杂度 O(1)

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (lists.length === 0) {
    return null;
  }

  return _mergeKLists(lists, 0, lists.length - 1);
}

// 主函数类似归并排序
function _mergeKLists(lists, low, high) {
  if (low >= high) {
    return lists[low];
  }

  // 1. 从中间切一刀
  let mid = Math.floor(low + (high - low) / 2);

  // 2. 递归的处理左边和右边的列表，然后合并起来
  return mergeTowLists(
    _mergeKLists(lists, low, mid),
    _mergeKLists(lists, mid + 1, high)
  );
}

// 合并链表的递归实现
function mergeTowLists(a, b) {
  if (a === null) {
    return b;
  }
  if (b === null) {
    return a;
  }

  if (a.val <= b.val) {
    a.next = mergeTowLists(a.next, b);
    return a
  } else {
    b.next = mergeTowLists(a, b.next);
    return b;
  }
}