LeetCode 23. 合并 K 个升序链表

2026-09-18 HGNULB 约 9 分钟

文章信息 31 个分类 4 个标签

分类

LeetCode CodeTop 困难已解决已掌握 200-500 LeetCode 热题 100 面试经典 150 题腾讯字节阿里华为微软亚马逊美团拼多多京东小米百度网易小红书快手滴滴 B站虾皮贝壳商汤旷视度小满猿辅导图森

题目描述

✅ 23. 合并 K 个升序链表

题意分析

给定 k 条已经按非递减顺序排列的链表，把它们的所有节点合并为一条仍然有序的链表并返回头节点。重复值需要全部保留；输入数组可能为空，其中某些链表也可能为空。

设所有链表共有 N 个节点。因为每条链表内部已经有序，没有必要取出所有值重新排序。可以每次从各链表剩余部分的头节点中选最小值，也可以不断把两条有序链表合成一条。下面两种实现都直接复用原节点，因此会修改原链表的连接。

解法一：最小堆多路归并

核心思路

[!blue]

每条非空链表中，当前头节点都不大于它后面的节点。因此所有尚未合并节点的最小值，一定出现在各条链表的当前头节点中。只比较这些候选，就能决定结果链表的下一个节点。

用最小堆维护候选，每条链表最多放入一个节点，堆顶就是全局最小的剩余节点。弹出堆顶接到结果末尾后，这条链表原来的头节点已经被取走，它的后继就成为新的候选；其他链表的候选保持不变。

这样堆始终代表所有还未处理完的链表。每次选出的值都不大于剩余节点，顺次连接即可保持结果有序；除初始化加入的各链表头节点外，每个节点只会在自己的前驱被取走后入堆，所以不会漏掉节点，也不会重复加入。

结果用哨兵 dummy 和尾指针 tail 维护，空结果也能直接执行 tail.next = node。连接当前节点后，立即把它的原后继加入堆；后续即使改写这个节点的 next，其原链表的剩余入口也已经由堆保存。堆清空时所有节点都已合并，返回 dummy.next；没有任何节点时它自然为空。

解题步骤

创建按节点值比较的最小堆，将所有非空链表的头节点加入堆。

创建哨兵 dummy，令 tail = dummy。

弹出堆顶 node，令 tail.next = node，再把 tail 移到该节点。

若 node 有后继，把后继加入堆，补上这条链表的新候选。

重复到堆为空，返回 dummy.next。

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!heap.isEmpty()) {
            // 各链表只提供当前头节点，堆顶就是全部剩余节点的最小值。
            ListNode node = heap.poll();

            tail.next = node;
            tail = node;

            // 只更新被取出链表的候选，不把全部节点提前入堆。
            if (node.next != null) {
                heap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

import "container/heap"

type nodeHeap []*ListNode

func (h nodeHeap) Len() int { return len(h) }

func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }

func (h nodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *nodeHeap) Push(value any) {
    *h = append(*h, value.(*ListNode))
}

// 标准堆先调整并把待弹元素移到末尾，这里只移除最后一项。
func (h *nodeHeap) Pop() any {
    old := *h
    last := len(old) - 1
    node := old[last]
    old[last] = nil
    *h = old[:last]
    return node
}

func mergeKLists(lists []*ListNode) *ListNode {
    minHeap := &nodeHeap{}
    heap.Init(minHeap)
    for _, node := range lists {
        if node != nil {
            heap.Push(minHeap, node)
        }
    }

    dummy := &ListNode{}
    tail := dummy
    for minHeap.Len() > 0 {
        // 各链表只提供当前头节点，堆顶就是全部剩余节点的最小值。
        node := heap.Pop(minHeap).(*ListNode)
        tail.Next = node
        tail = node

        // 只更新被取出链表的候选，不把全部节点提前入堆。
        if node.Next != nil {
            heap.Push(minHeap, node.Next)
        }
    }
    return dummy.Next
}

复杂度分析

时间复杂度：$O(k+N\log(k+1))$，先检查 k 条链表的头，再逐个处理 N 个节点；空链表也需要检查。

空间复杂度：$O(k)$，用于保存每条链表的当前候选节点。

关键点总结

[!green]

堆中每条非空链表最多保留一个候选节点。

弹出节点后必须加入它的后继，才能继续归并该链表。

直接复用原链表节点，只修改 next 指针，不需要复制节点。

比较器使用 Integer.compare，避免相减造成整数溢出。

解法二：两两合并 + 倍增

核心思路

[!blue]

两条有序链表可以用双指针线性合并：比较它们当前的头节点，把较小者接到结果末尾，并只推进这一侧。较小的头节点不大于两条链表的其他剩余节点，因此这个选择不会破坏有序性；一侧耗尽后，另一侧的剩余部分可以整体接上。

将这个过程扩展到 k 条链表时，不要一直把越来越长的结果与下一条链表合并，那会反复扫描同一批节点。采用成对归并：先把相邻的单条链表合并，再把相邻的两组结果合并，每轮负责的原始链表数量翻倍。

用 step 表示当前每个已合并分组覆盖的原始链表数量，初始为 1。一轮开始时，每个分组的合并结果保存在该组起点 lists[i]；把它与下一组起点 lists[i + step] 合并后，结果写回 lists[i]。这就将最多两组的全部节点保存到了更大分组的起点。

本轮处理下一对分组时，i 增加 2 * step，保证分组不重叠；若第二组不存在，第一组原样留下即可，后续更大跨度的一轮会再与它合并。虽然数组里的其他旧头指针没有清空，后续只读取新的分组起点，不会重复合并旧分组。

每轮结束令 step 翻倍，经过对数轮后，一个分组就覆盖了全部链表，答案保存在 lists[0]。每一轮中各组合并互不重叠，每个节点最多参与一次归并，从而把节点被反复处理的次数控制在对数量级。

解题步骤

令 step = 1，表示每组最初只有一条原始链表。

在本轮中从 i = 0 开始，只要 i + step < k，就合并 lists[i] 与 lists[i + step]，将结果写回 lists[i]。

合并时使用尾指针连接较小的头节点，推进对应链表；一侧为空后，接上另一侧的全部剩余节点。

i 每次增加 2 * step；本轮结束后将 step 翻倍，继续合并更大的分组。

当 step >= k 时结束，返回 lists[0]；若输入数组为空，则直接返回空节点。

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 每轮合并范围翻倍，让各节点只参与对数轮归并。
        for (int step = 1; step < lists.length; step *= 2) {
            // 只有第二组存在才合并，不足两组时保留原结果。
            for (int i = 0; i + step < lists.length; i += step * 2) {
                // 两组不重叠，合并结果写回本组起点供下一轮使用。
                lists[i] = merge(lists[i], lists[i + step]);
            }
        }

        return lists.length == 0 ? null : lists[0];
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (a != null && b != null) {
            if (a.val <= b.val) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }

            tail = tail.next;
        }

        tail.next = a != null ? a : b;

        return dummy.next;
    }
}

func mergeKLists(lists []*ListNode) *ListNode {
    // 每轮合并范围翻倍，让各节点只参与对数轮归并。
    for step := 1; step < len(lists); step *= 2 {
        // 只有第二组存在才合并，不足两组时保留原结果。
        for i := 0; i+step < len(lists); i += step * 2 {
            // 两组不重叠，合并结果写回本组起点供下一轮使用。
            lists[i] = merge(lists[i], lists[i+step])
        }
    }
    if len(lists) == 0 {
        return nil
    }
    return lists[0]
}

func merge(a, b *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for a != nil && b != nil {
        if a.Val <= b.Val {
            tail.Next = a
            a = a.Next
        } else {
            tail.Next = b
            b = b.Next
        }
        tail = tail.Next
    }
    if a != nil {
        tail.Next = a
    } else {
        tail.Next = b
    }
    return dummy.Next
}

复杂度分析

时间复杂度：上界为 $O(k+N\log(k+1))$，包含分组遍历与节点归并；k = 1 时直接返回原链表。

空间复杂度：$O(1)$，迭代合并复用节点，并把每组结果写回 lists。

关键点总结

[!green]

平衡合并：避免把不断变长的结果与下一条链表逐一合并。

余组留到下一轮：只有 i + step < k 才有配对，奇数条链表不会丢失。

输入会改变：节点连接和 lists 中保存的头指针都会更新。

易错点总结

[!yellow]

两两合并要按轮次配对：每轮跨度翻倍，不能始终拿累积结果与下一条合并，否则总比较次数可能达到 $O(Nk)$。

将空链表放入 Java 的优先队列会抛出异常。

弹出节点后忘记把后继入堆，会丢失该链表剩余部分。

一次把所有节点放入堆会把空间从 $O(k)$ 扩大到 $O(N)$。

比较器写成 a.val - b.val 可能发生整数溢出。

相似题目

题目	难度	关联与区别
21. 合并两个有序链表	简单	两两归并是分治合并k条链表的基本子过程。
373. 查找和最小的 K 对数字	中等	同样按各路当前最小候选进行堆归并，原题的每一路是数对和序列。
148. 排序链表	中等	按有序头节点逐步拼接链表；本题用小顶堆或分治扩展到多条链表，该题以归并排序反复合并子链表。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/59897639

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！