3.合并 K 个有序链表

LeetCode 第 23 题 合并 K 个有序链表

题目

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

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

示例 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

解题思路

1. list 的每一个链表都是升序
2. 与合并两个升序链表思路相近

解法1

循环 list，每次找到 list 内最小的值，赋值到新链表，这种解法肯定可以，时间复杂度为 O(NK)，因为节点总数为 N，链表总数为 K，每次找到一个节点，需要遍历链表 K 次，所有节点都找到那么则是 N * K， 因此时间复杂度是 O(NK)。这是暴力解法，所以时间复杂度还是较高的。

/**
 * 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 head = new ListNode();
  // 迭代指针
  let p = head;
  // 不设置条件，先循环，内部达到条件后 break 即可
  while (true) {
    // 当前最小值节点
    let currentMinNode;
    // 当前链表所在 list 索引
    let currentIndex;
    // 遍历链表
    for (let i = 0; i < lists.length; i++) {
      // 如果没有节点 说明第一次进入循环
      if (!currentMinNode) {
        // 赋值当前最小节点以及所在 list 索引
        currentMinNode = lists[i];
        currentIndex = i;
        continue;
      }
      // 比较当前和上一次的最小值，如果更小则替换
      if (lists[i]?.val < currentMinNode.val) {
        currentMinNode = lists[i];
        currentIndex = i;
      }
    }
    // 经过遍历得到最小值
    if (lists[currentIndex]) {
      // 把最小值的链条向前走迭代
      lists[currentIndex] = lists[currentIndex].next;
    }
    // 遍历完成

    // 如果没有最小值的节点，说明所有链表循环完成
    if (!currentMinNode) {
      // 跳出循环
      break;
    } else {
      // 当前链表向前迭代 next
      p.next = currentMinNode;
      p = p.next;
    }
  }
  return head.next;
};

解法2

使用二分法把有序链表合并成一条链表，不断递归，类似快速排序不断二分合并。 K 个链表二分的次数为 log2K，假设每次二分合并的个数为最长节点 N，那么时间复杂度是 O(NlgK)，在时间复杂度上，底数 2 可以省略。

/**
 * 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) {
  // 这是第二题的合并两个有序链表的解法，时间复杂度为 N
  function mergeToLists(lists1, lists2) {
    let p1 = lists1;
    let p2 = lists2;
    let p = new ListNode(-1);
    const head = p;
    while (p1 && p2) {
      if (p1.val < p2.val) {
        p.next = p1;
        p1 = p1.next;
      } else {
        p.next = p2;
        p2 = p2.next;
      }
      p = p.next;
    }
    if (p1) {
      p.next = p1;
    }
    if (p2) {
      p.next = p2;
    }
    return head.next;
  }
  // 分割列表，输入为列表的头尾
  function dls(start, end) {
    // 头尾距离差
    const d = end - start;
    // 头尾距离 0，没有节点
    if (d === 0) return null;
    // 距离 1 有一个节点，因为 end 是开区间，不包含 end
    if (d === 1) return lists[start];
    // 找到中间值
    const mid = Math.floor(d / 2);
    // 如果节点超过 1 个，递归二分直到分为一个一个的为止
    const left = dls(start, start + mid);
    const right = dls(start + mid, end);
    // 递归完成后，调用合并列表
    return mergeToLists(left, right);
  }

  return dls(0, lists.length);
};