力扣-23. 合并 K 个排序链表（Merge k Sorted Lists）

最后编辑于2025-07-16

23. 合并 K 个排序链表（Merge k Sorted Lists）

Hard

给定一个包含 k 个链表的数组 lists，每个链表都按升序排列。将所有链表合并为一个升序链表并返回合并后的链表头结点。

示例 1：

输入： lists = [[1,4,5],[1,3,4],[2,6]]
输出： [1,1,2,3,4,4,5,6]
解释： 链表分别为 1->4->5, 1->3->4, 2->6，合并后为 1->1->2->3->4->4->5->6。

示例 2：

输入： lists = []
输出： []

示例 3：

输入： lists = [[]]
输出： []

约束：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • 每个 lists[i] 已按升序排列
  • 所有链表长度之和不会超过 10^4

总体思路与常见解法

合并 k 个有序链表可以用多种策略：

  • 两两合并（分治 / 对折合并）：不断把链表两两配对合并，缩减问题规模，类似归并排序的合并过程，时间复杂度为 O(N log k)，其中 N 为总节点数，k 为链表数。
  • 最小堆（优先队列）：将每个链表的当前最小节点放入最小堆，每次取堆顶加入结果并把该节点的下一个节点放入堆，时间复杂度为 O(N log k)，空间复杂度 O(k)。
  • 直接顺序合并（累积合并）：逐个把链表合并到结果中，最坏 O(kN)，一般不优。
  • 计数/桶排序法（当值域较小时可用）：统计每个值出现次数，再按值域重建链表。适合值域小、允许新建节点的场景。

下面给出几种常见实现（均为 C++）。

方法一：迭代分治（两两合并，in-place）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        int n = lists.size();
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[i + k]);
            }
            n = k;
        }
        return lists[0];
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(-1), *cur = &dummy;
        while (l1 && 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 ? l1 : l2;
        return dummy.next;
    }
};
  • 时间复杂度： O(N log k)
  • 空间复杂度： O(1)（不计答案所需空间）

方法二：优先队列（最小堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 node : lists) if (node) pq.push(node);
        ListNode dummy(-1), *cur = &dummy;
        while (!pq.empty()) {
            auto t = pq.top(); pq.pop();
            cur->next = t; cur = cur->next;
            if (t->next) pq.push(t->next);
        }
        return dummy.next;
    }
};
  • 时间复杂度： O(N log k)
  • 空间复杂度： O(k)

方法三：递归分治（归并排序式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        return helper(lists, 0, lists.size() - 1);
    }
    ListNode* helper(vector<ListNode*>& lists, int l, int r) {
        if (l > r) return NULL;
        if (l == r) return lists[l];
        int mid = l + (r - l) / 2;
        ListNode* left = helper(lists, l, mid);
        ListNode* right = helper(lists, mid + 1, r);
        return mergeTwoLists(left, right);
    }
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        if (!a) return b; if (!b) return a;
        if (a->val < b->val) { a->next = mergeTwoLists(a->next, b); return a; }
        else { b->next = mergeTwoLists(a, b->next); return b; }
    }
};
  • 时间复杂度： O(N log k)
  • 空间复杂度： O(log k)（递归栈）

方法四：计数排序（重建链表，适用于值域小且允许新建结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy(-1), *cur = &dummy;
        unordered_map<int,int> cnt;
        int mn = INT_MAX, mx = INT_MIN;
        for (auto node : lists) {
            for (ListNode* t = node; t; t = t->next) {
                ++cnt[t->val]; mn = min(mn, t->val); mx = max(mx, t->val);
            }
        }
        for (int v = mn; v <= mx; ++v) {
            if (!cnt.count(v)) continue;
            for (int c = 0; c < cnt[v]; ++c) {
                cur->next = new ListNode(v);
                cur = cur->next;
            }
        }
        return dummy.next;
    }
};
  • 说明： 该法在值域较小、允许新建结点时非常快；否则受限于值域范围与内存开销。

作者想说的话：
合并 k 个有序链表的常用高效方案是分治（两两合并）与最小堆。两者时间复杂度都为 O(N log k)，常在工程中交替使用：当 k 很大且内存敏感时优先考虑分治；当 k 较大且需要在线合并（流式数据）时优先使用最小堆。计数重建在值域受限且允许重建节点的特殊场景也很实用。