链表篇（三）——合并K个升序链表

2501_90419475

572人浏览 · 2026-05-03 14:52:42

2501_90419475 · 2026-05-03 14:52:42 发布

一、题目本质

核心模型：K 路归并 —— 两路归并的泛化，典型的多路合并问题。

二、解法

1.优先队列实现

ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [] (ListNode * a, ListNode * b){ return a->val > b->val;};
        priority_queue<ListNode *, vector<ListNode*>, decltype(cmp)> pq(cmp);

        // 每个链表的头节点入队列
        for(auto head : lists)
        {
            if(head) pq.push(head);
        }

        // 创建虚拟头节点
        ListNode dummy(0);
        ListNode * tail = & dummy;

        while(! pq.empty())
        {
            ListNode * node = pq.top();
            pq.pop();
            tail->next = node;
            tail = tail->next;
            if(node->next) pq.push(node->next);
        } 
        return dummy.next;
    }

复杂度分析：

时间：O(N log K)，N 是总节点数，每次堆操作 O(log K)
空间：O(K)，堆中最多有 K 个结点

特点：值越小的链表越会被频繁弹出，堆会不断从该链表补充下一个结点。像 K 个水龙头放水，每次取当前水量最小的那个接一滴。

2.分治归并实现

ListNode* mergeTwoLists(ListNode* a, ListNode* b)
    {
        // 创建虚拟头节点
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while(a && b)
        {
            ListNode** smaller = (a->val <= b->val)? &a : &b;
            ListNode* node = *smaller;
            *smaller = (*smaller)->next;
            tail->next = node;
            tail = tail->next;
        }
        tail->next = a? a : b;
        return dummy.next;
    }
    ListNode* merge(vector<ListNode*>& lists, int l, int r)
    {
        if(l == r) return lists[l];
        else if(l > r) return nullptr;
        int mid = (l + r) >> 1;
        // 合并左，合并右， 左右两边合并
        ListNode* left = merge(lists, l, mid);
        ListNode* right = merge(lists, mid + 1, r);
        return mergeTwoLists(left, right);
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr; 
       return merge(lists,  0, lists.size() - 1);
    }

复杂度分析：

时间：O(N log K)，归并树有 log K 层，每层合并 N 个结点
空间：O(log K)，递归栈深度

        [l1, l2, l3, l4]
        /             \
   [l1, l2]         [l3, l4]
   /      \         /      \
 l1       l2       l3       l4
  \      /         \      /
   合并             合并
      \            /
          最终合并

特点：每个链表参与合并的次数均等（都是 log K 次），不会有某个很长的链表一直被反复遍历的问题。

3.逐一合并

    ListNode* mergeTwoLists(ListNode* a, ListNode* b)
    {
        // 创建虚拟头节点
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while(a && b)
        {
            ListNode** smaller = (a->val <= b->val)? &a : &b;
            ListNode* node = *smaller;
            *smaller = (*smaller)->next;
            tail->next = node;
            tail = tail->next;
        }
        tail->next = a? a : b;
        return dummy.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* result = nullptr;
    for (ListNode* head : lists) {
        result = mergeTwoLists(result, head);  // 把新链表串行合并到结果上
    }
    return result;
}

复杂度：O(N·K)，最坏情况第一个链表极长，每次都要完整遍历它。

三、复杂度分析

四、变形训练

变形1：K 个降序链表合并为降序

要求：输入是 K 个降序链表，输出也是降序。

（1）方法一：优先队列（大顶堆）

（2）方法二：分治法（修改合并两个链表的逻辑）

变形2：流式输入（链表一条一条来）

场景：K 个链表不是一次性给全的，而是一条一条到达，要求随时能输出当前已合并的结果。

（1）方法一：逐一合并（适合 K 小）

class StreamingMerge {
    ListNode* result = nullptr;
public:
    void add(ListNode* list) {
        result = mergeTwoLists(result, list);  // 复用 21 题的合并
    }
    ListNode* getResult() {
        return result;
    }
};

来一个链表，就和当前结果合并一次；最后直接拿结果。

（2）方法二：维护堆（适合流式、数据量大）

场景：时间线合并、日志聚合、搜索引擎结果合并 —— 一条一条拉取，而不是一次性全合并。

class StreamingMerge {
private:
    // 小顶堆：存每个链表"当前头部"
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq{cmp};
    
    // 累积结果的链条
    ListNode dummy(0);
    ListNode* tail = &dummy;

public:
    // 注册一个新数据源（链表）
    void addList(ListNode* list) {
        if (list) pq.push(list);
    }
    
    // 获取当前最小的一个结点（逐个消费）
    ListNode* getNext() {
        if (pq.empty()) return nullptr;
        
        ListNode* node = pq.top();
        pq.pop();
        
        if (node->next) pq.push(node->next);  // 这个源的下一结点入堆
        
        // 接到结果链上
        tail->next = node;
        tail = node;
        tail->next = nullptr;
        
        return node;
    }
    
    // 一次性消费完所有剩余结点，返回合并后的完整链表
    ListNode* getAll() {
        while (!pq.empty()) getNext();
        return dummy.next;
    }
};

使用示例：

StreamingMerge sm;

sm.addList(list1);  // 1 → 4 → 5
sm.addList(list2);  // 2 → 6

ListNode* node1 = sm.getNext();  // 返回 1
ListNode* node2 = sm.getNext();  // 返回 2

// 又来一个新数据源
sm.addList(list3);  // 3 → 7

ListNode* rest = sm.getAll();  // 返回 3 → 4 → 5 → 6 → 7

变形3：只返回合并后的前 M 个结点

场景：K 个热搜榜单合并，只需要前 100 条。

ListNode* mergeKListsTopM(vector<ListNode*>& lists, int M) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    
    for (auto head : lists) {
        if (head) pq.push(head);
    }
    
    ListNode dummy(0);
    ListNode* tail = &dummy;
    int count = 0;
    
    while (!pq.empty() && count < M) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node;
        tail = tail->next;
        count++;
        if (node->next) pq.push(node->next);
    }
    
    tail->next = nullptr;  // 截断
    return dummy.next;
}

不需要处理所有结点，提前终止即可。大幅节省时间

五、模型迁移

外排序多路归并

当数据大到内存装不下时：

分块排序：把大文件切成K块，每块读入内存排序后写回磁盘
多路归并：从K个有序块各读一小段到输入缓冲区
败者树/堆：每次选K个缓冲区中最小的元素输出到结果文件
某缓冲区空了，从对应块再读一段

核心与 mergeKLists 完全一致，只是链表结点变成了文件缓冲区的元素。

六、自检

能闭眼写出优先队列版本，cmp 不出错
能闭眼写出分治归并版本，递归终止条件不出错
能解释逐一合并为什么是 O(N·K)
能画出 K=4 的归并树分治过程
能改成去重合并 / 降序合并
能讲出堆方法在外部排序中的应用

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

【Agent智能体4 | 智能体AI的应用】

AtomGit开源社区

周报5.24

一句话总结：该论文全面综述了基于深度学习的视觉可用性识别（Visual Affordance Recognition）方法，展示了其在机器人技术、人机交互和其它视觉任务中的应用价值，并强调了MAE模型作为一种可扩展的自监督学习方法，为复杂场景中的可用性识别提供了新思路。贡献列表系统性综述：涵盖了可用性识别的五个主要任务（分类、检测、分割、行为识别与推理），并通过详细的技术分类展示不同方法的优劣和设

AtomGit开源社区

关于Spring AI Alibaba

Spring AI在2024年2月发布了第一个公开可用版本。从此Java有了官方支持的AI框架，相对于LangChain4J，Spring AI天生建立在Spring的基础上，与Spring和SpringBoot的结合更加的紧密。2024年9月，阿里云开源了Spring AI Alibaba，这个项目已经发布了1.0 GA正式版，并在阿里双11核心系统中验证，支持每秒百万级智能体交互，平均决策延迟