LeetCode LCR 078. 合并 K 个升序链表

约 9 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
LCR 链表 堆（优先队列） 分治 归并排序

题目描述

✅ LCR 078. 合并 K 个升序链表

image-20260929005834706

image-20260929005834713

题意分析

输入 k 条已按升序排列的链表，将它们合并为一条升序链表。可以复用原节点并修改连接，不需要复制全部节点。

链表数组可能为空，数组中也可能有空链表。关键是利用每条链已有的顺序：既可以在各链的当前头节点之间选最小值，也可以将链表两两归并。

解法一：最小堆按头节点归并

核心思路

[!blue]

每条链的当前头节点都是该链剩余部分的最小值。因此，所有未合并节点中的最小值，一定在这些头节点之中，不必比较链表内部的其他节点。

用最小堆维护每条未耗尽链表的一个头节点。每次弹出堆顶接到结果末尾，再把该节点的后继放入堆中，更新它所在链的候选。这样堆始终保存各条剩余链的最小值，结果前缀始终有序。

堆为空时，所有链都已耗尽。最后接入的节点必然没有后继，否则它的后继还会入堆，所以结果尾部自然为空。输入全为空时，哨兵的后继仍为空，直接得到空链表。

Go 的自定义 Pop 删除切片末项，是因为 container/heap 会先把堆顶换到末尾，再调用这个方法；取最小值要调用 heap.Pop，不能直接调用底层 Pop。

解题步骤

  1. 创建按节点值比较的最小堆，将所有非空链表头入堆。
  2. 创建哨兵 dummy，令 tail 指向当前结果尾部。
  3. 弹出最小节点，接到 tail 后并移动尾指针。
  4. 若该节点有后继，将后继入堆，继续参与比较。
  5. 堆为空时返回 dummy.next。

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap =
                new PriorityQueue<>((first, second) -> Integer.compare(first.val, second.val));

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

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

        while (!minHeap.isEmpty()) {
            // 堆顶就是当前所有链表头节点中最小的节点。
            ListNode node = minHeap.poll();

            tail.next = node;
            tail = tail.next;

            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

import (
    "container/heap"
)

type ListNodeHeap []*ListNode

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

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

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

func (h *ListNodeHeap) Push(x any) {
    *h = append(*h, x.(*ListNode))
}

func (h *ListNodeHeap) Pop() any {
    old := *h
    node := old[len(old)-1]
    *h = old[:len(old)-1]
    return node
}

func mergeKLists(lists []*ListNode) *ListNode {
    minHeap := &ListNodeHeap{}
    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 = tail.Next
        if node.Next != nil {
            heap.Push(minHeap, node.Next)
        }
    }

    return dummy.Next
}

复杂度分析

设入口数为 k、非空链表数为 h、节点总数为 n。

  • 时间复杂度：$O(k+n\log(h+1))$。先检查全部入口，每个节点入堆、出堆各一次，堆中至多有 h 个节点。
  • 空间复杂度：$O(h)$，用于候选堆；结果复用原节点。

关键点总结

[!green]

  • 堆里只放每条剩余链的当前头节点，候选数由链表条数决定。
  • 必须保存节点而非仅保存值，弹出后才能找到它的后继。
  • 链表条数可能大于节点总数，复杂度不能漏掉检查空入口的开销。

解法二：分治归并链表

核心思路

[!blue]

两条有序链表可以在线性时间内合并。若总把已合并的长链与下一条链合并，前面的节点会被反复处理；改为将链表编号区间对半划分，再逐层两两合并，就能把每个节点参与的层数限制在 $O(\log k)$。

定义 mergeRange(lists, left, right) 返回编号区间 [left, right] 内所有节点组成的有序链。区间只含一条链时，它本身就是答案；否则递归合并左右两半，再将这两个有序结果归并，便得到整个区间的答案。

两路归并时不断取较小的头节点接到 tail 后。一条链耗尽后，另一条剩余部分已经有序，且不小于已接入节点，可以整体接上。值相同时优先取左链，保留同值节点的先后次序。

解题步骤

  1. 链表数组为空时直接返回空，避免构造无效编号区间。
  2. 对完整编号区间调用 mergeRange；只有一个入口时直接返回该链，包括空链。
  3. 从中点分成左右两段，分别递归得到有序链。
  4. 比较两条链的当前头节点，将较小者接到结果末尾。
  5. 接上未耗尽的一整段，返回哨兵后继。

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

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

    private ListNode mergeRange(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }

        int mid = left + (right - left) / 2;
        ListNode first = mergeRange(lists, left, mid);
        ListNode second = mergeRange(lists, mid + 1, right);

        return mergeTwoLists(first, second);
    }

    private ListNode mergeTwoLists(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (first != null && second != null) {
            // 每次只接入两条链表当前头节点中更小的那个。
            if (first.val <= second.val) {
                tail.next = first;
                first = first.next;
            } else {
                tail.next = second;
                second = second.next;
            }

            tail = tail.next;
        }

        if (first != null) {
            tail.next = first;
        } else {
            tail.next = second;
        }

        return dummy.next;
    }
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    return mergeRange(lists, 0, len(lists)-1)
}

func mergeRange(lists []*ListNode, left int, right int) *ListNode {
    if left == right {
        return lists[left]
    }

    mid := left + (right-left)/2
    first := mergeRange(lists, left, mid)
    second := mergeRange(lists, mid+1, right)
    return mergeTwoLists(first, second)
}

func mergeTwoLists(first *ListNode, second *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for first != nil && second != nil {
        // 每次只接入两条链表当前头节点中更小的那个。
        if first.Val <= second.Val {
            tail.Next = first
            first = first.Next
        } else {
            tail.Next = second
            second = second.Next
        }
        tail = tail.Next
    }

    if first != nil {
        tail.Next = first
    } else {
        tail.Next = second
    }

    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(k+n\log(k+1))$ 上界。遍历编号区间形成的递归树需 $O(k)$，各合并层最多处理 $O(n)$ 个节点，共 $O(\log(k+1))$ 层；全部链为空时也仍有入口处理开销。
  • 空间复杂度：$O(\log(k+1))$，来自递归栈；两路归并只用常数个指针。

关键点总结

[!green]

  • 对半划分的是链表编号，不需要预先计算每条链的长度。
  • 每层先得到两个有序结果，再使用两路归并，正确性由子问题逐层建立。
  • 未耗尽的后缀可以整体挂接，不必逐个复制节点。

解法对比：

堆法维护每条链的当前候选，适合逐个取出全局最小节点；分治法按编号组织两两合并。两者都复用原节点，额外空间分别来自堆和递归栈。

易错点总结

[!yellow]

  • 堆中跳过空链，弹出节点后别遗漏它的后继。
  • 分治前先处理空数组，归并结束后接回剩余链段。
  • 堆法比较的是节点值，值相等的不同节点都应保留。
  • 两种方法的复杂度都要计入空链入口，不能默认 k <= n。

相似题目

题目 难度 关联与区别
21. 合并两个有序链表 简单 两两归并是分治合并k条链表的基本子过程。
373. 查找和最小的 K 对数字 中等 同样按各路当前最小候选进行堆归并，原题的每一路是数对和序列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/67254571
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！