合并 K 个升序链表

GitHub跳转原题关系图返回列表

小根堆维护每条链当前头节点，每次弹出后推进，O(N log K)。

OJ: leetcodecn

题目 ID: merge-k-sorted-lists

难度:提高+/省选-

标签:链表堆分治cpppython

日期: 2026-07-28 22:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

合并 k 个升序链表，返回一个升序链表。

思路

分治两两合并 O(N log K)。堆方法：把所有链表的头节点放入小根堆，每次弹出最小值节点加入结果，并将该节点的 next 入堆。每个节点入堆出堆各一次，O(N log K)。

代码

cpp
/**
 * Author by Rainboy
 */
// main.cpp：小根堆 O(N log K)。
#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    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 h : lists)
            if (h)
                pq.push(h);
        ListNode dummy(0), *cur = &dummy;
        while (!pq.empty()) {
            auto node = pq.top();
            pq.pop();
            cur->next = node;
            cur = cur->next;
            if (node->next)
                pq.push(node->next);
        }
        return dummy.next;
    }
};

ListNode *build(istream &in, int n) {
    if (!n)
        return nullptr;
    auto head = new ListNode(0), cur = head;
    for (int i = 0, v; i < n; i++) {
        in >> v;
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return head->next;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> k;
    vector<ListNode *> lists(k);
    for (int i = 0; i < k; i++) {
        int n;
        cin >> n;
        lists[i] = build(cin, n);
    }
    auto head = Solution().mergeKLists(lists);
    for (auto p = head; p; p = p->next)
        cout << p->val << ' ';
    return 0;
}
python
#!/usr/bin/env python3
import heapq
from typing import List, Optional


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        pq = []
        for i, h in enumerate(lists):
            if h:
                heapq.heappush(pq, (h.val, i, h))
        dummy = cur = ListNode(0)
        while pq:
            _, i, node = heapq.heappop(pq)
            cur.next = node
            cur = cur.next
            if node.next:
                heapq.heappush(pq, (node.next.val, i, node.next))
        return dummy.next


def build(arr):
    dummy = cur = ListNode(0)
    for v in arr:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


def main() -> None:
    k = int(input())
    lists = []
    for _ in range(k):
        n = int(input())
        a = list(map(int, input().split()))
        lists.append(build(a))
    head = Solution().mergeKLists(lists)
    while head:
        print(head.val, end=" ")
        head = head.next


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(N log K)，N 为总节点数，K 为链表数。
  • 空间复杂度：O(K)，堆的大小。

总结

"多路归并用小根堆维护 k 个候选"是处理多路有序数据合并的标准模型。