力扣百题通

23. 合并 K 个升序链表 (Hard)

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

7分钟阅读

23. 合并 K 个升序链表 (Hard)

专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/merge-k-sorted-lists/

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例：

  • 输入：lists = [[1,4,5],[1,3,4],[2,6]]
  • 输出：[1,1,2,3,4,4,5,6]

题目详细分析

  • 数据范围： K = lists.length 在 [0, 10^4] 范围内，每个链表长度在 [0, 500] 范围内，总节点数在 [0, 10^4] 范围内
  • 输入特征： 一个链表数组，每个链表都已升序排列，但长度可能为 0
  • 核心约束： 需要高效合并 K 个链表，不能简单把所有值取出再排序
  • 隐藏条件： K 可能很大（10^4），所以 O(K * N) 的每次选最小法会超时；每个链表的头部就是当前最小值候选
  • 边界条件： 空数组、数组中有空链表、K = 1（直接返回）、所有链表都为空

小白版直白理解

现在有 K 叠已经按大小排好序的扑克牌，要把它们合并成一叠。

最笨的方法：每次从 K 叠牌的顶部分别看一眼，找出最小的那张拿走。但看 K 眼才能找到最小，太慢了。

聪明的方法：把这些牌摆成一个「擂台」（最小堆），每叠牌最上面那张先上擂台比一轮，最小的那张直接出列。然后它后面的牌上擂台补位，再比一轮。这样每次只需要比较 log(K) 次就能找到最小。

另一种思路：先两两合并，最后只剩一叠。就像淘汰赛，第一轮 K/2 场、第二轮 K/4 场……每场合并两个有序链表。

解题思路

思路一：最小堆法（推荐）

为什么这样想： 每次从 K 个链表的头节点中取最小值，最直接的做法是遍历 K 个头找最小，O(K) 每次，总复杂度 O(NK)。用最小堆可以将找最小优化到 O(log K)。堆中始终维护当前 K 个链表当前的头节点。

关键洞察： Python 的 heapq 不支持直接比较 ListNode 对象，所以需要在堆中存入 (node.val, index, node) 三元组。其中 index 用于处理值相等时避免比较 ListNode 对象。

import heapq
 
def mergeKLists(lists):
    """最小堆法"""
    dummy = ListNode(0)
    cur = dummy
    heap = []
    
    # 将所有链表的头节点加入堆
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    
    while heap:
        val, i, node = heapq.heappop(heap)  # 取出最小节点
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

思路二：分治法（两两合并）

思路讲解： 将 K 个链表「两两配对合并」，每轮合并后链表数减半。重复直到只剩一个链表。每次合并复用 21 题的 mergeTwoLists 函数。

关键洞察： 分治法的复杂度分析和最小堆法一样都是 O(N log K)。每层合并的总节点数是 N，共有 log K 层。分治法的空间复杂度取决于递归深度 O(log K)。

def mergeKLists(lists):
    """分治法：两两合并"""
    if not lists:
        return None
    if len(lists) == 1:
        return lists[0]
    
    mid = len(lists) // 2
    left = mergeKLists(lists[:mid])
    right = mergeKLists(lists[mid:])
    return mergeTwoLists(left, right)
 
 
def mergeTwoLists(l1, l2):
    """合并两个有序链表"""
    dummy = ListNode(0)
    cur = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 if l1 else l2
    return dummy.next

思路三：顺序合并（最朴素）

思路讲解： 维护一个结果链表，依次将每个链表合并到结果中。先合并 lists[0] 和 lists[1]，结果再和 lists[2] 合并，以此类推。时间复杂度 O(NK) —— 前 i 次合并的链表越来越长，效率最低。

def mergeKLists(lists):
    """顺序合并（效率最低）"""
    if not lists:
        return None
    
    result = lists[0]
    for i in range(1, len(lists)):
        result = mergeTwoLists(result, lists[i])
    return result

易错点

  • 堆中存入三元组： 不能只存 (node.val, node)，因为 heapq 在 val 相同时会尝试比较 node（ListNode 对象），而 ListNode 没有定义比较操作，会报错。用 (val, index, node) 三元组解决
  • 空链表处理： 链表数组中可能有空链表（None），在加入堆和分治时都要跳过
  • lists 为空： 如果 lists 是空数组，直接返回 None
  • 分治法的截止条件： len(lists) == 1 返回 lists[0]，不是返回 head
  • 堆的更新： 弹出最小节点后，如果它的 next 不为空，要立即将 next 节点入堆

框架提炼

K 路归并模板： 两个主流方法——最小堆和分治。

最小堆法模板：

import heapq
 
def merge_k_lists(lists):
    dummy = ListNode(0)
    cur = dummy
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    while heap:
        _, _, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))  # 注意：i 需要提前保存
    return dummy.next

分治法模板：

def merge_k_lists(lists):
    if not lists: return None
    if len(lists) == 1: return lists[0]
    mid = len(lists) // 2
    left = merge_k_lists(lists[:mid])
    right = merge_k_lists(lists[mid:])
    return merge_two(left, right)

最小堆适合「动态取最小」的场景，分治适合「静态批量合并」的场景。两者的时间复杂度和空间复杂度基本一致。

关联题目

关系图谱

反向链接