23. 合并 K 个升序链表

题目描述

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

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

例如：

输入：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 为链表数组 lists 的长度。
每条链表中的节点值均为整数。
需要保证最终结果仍然按升序排列。

实现思路

这题可以看作是“合并两个有序链表”的扩展。直接把每条链表依次合并到结果中，最坏情况下会重复遍历大量节点；更合适的做法是使用分治：

将 k 条链表两两合并，得到约 k / 2 条链表。
继续两两合并，直到只剩一条链表。
每一轮都会遍历所有节点一次，共有 O(log k) 轮。

合并两条链表时直接复用原节点，不需要创建新的节点。使用哨兵节点可以统一处理结果链表为空以及头节点连接等边界情况。

代码实现

var mergeKLists = function (lists) {
  if (lists.length === 0) return null;

  const mergeTwoLists = (list1, list2) => {
    const dummy = new ListNode(0);
    let current = dummy;

    while (list1 && list2) {
      if (list1.val <= list2.val) {
        current.next = list1;
        list1 = list1.next;
      } else {
        current.next = list2;
        list2 = list2.next;
      }
      current = current.next;
    }

    current.next = list1 || list2;
    return dummy.next;
  };

  // 每轮将相邻的两条链表合并，直到只剩一条链表
  while (lists.length > 1) {
    const mergedLists = [];

    for (let i = 0; i < lists.length; i += 2) {
      const list1 = lists[i];
      const list2 = lists[i + 1] || null;

      mergedLists.push(mergeTwoLists(list1, list2));
    }

    lists = mergedLists;
  }

  return lists[0] || null;
};

复杂度分析

设所有链表共有 n 个节点，链表数量为 k：

时间复杂度：O(n log k)，每一轮合并都会遍历全部节点，共 log k 轮。
空间复杂度：O(k)，每一轮使用临时数组保存合并后的链表；合并节点本身没有额外创建。

边界情况

lists 为空时，直接返回 null。
lists 中包含空链表时，合并函数会自动跳过空链表。
只有一条链表时，直接返回这条链表。
节点值相同时优先连接 list1，但这不影响最终结果的有序性。

ON THIS PAGE

#23. 合并 K 个升序链表

#题目描述

#实现思路

#代码实现