合并 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] 按升序排列
• lists[i].length 的总和不超过 10^4

解法一（优先队列）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Compare {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;

        for (ListNode* head : lists)
        {
            if (head != nullptr)
            {
                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 != nullptr)
            {
                pq.push(node->next);
            }
        }

        return dummy.next;
    }
};

解法二（分治合并）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
        {
            return nullptr;
        }

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

private:
    ListNode* mergeRange(vector<ListNode*>& lists, int left, int right) {
        if (left == right)
        {
            return lists[left];
        }

        int mid = left + (right - left) / 2;
        ListNode* list1 = mergeRange(lists, left, mid);
        ListNode* list2 = mergeRange(lists, mid + 1, right);

        return mergeTwoLists(list1, list2);
    }

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (list1 != nullptr && list2 != nullptr)
        {
            if (list1->val <= list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }

            tail = tail->next;
        }

        tail->next = list1 != nullptr ? list1 : list2;

        return dummy.next;
    }
};

核心思想

这题是“合并两个有序链表”的扩展。

现在不是两个链表，而是 k 个链表。

最直接的想法是反复合并：

• 先合并第 1 个和第 2 个
• 再把结果和第 3 个合并
• 继续合并到最后

这样可以做，但如果某个中间结果越来越长，后面每次合并都会反复扫描它，效率不够稳定。

更常用的做法有两种：

1. 使用优先队列，每次取所有链表当前头节点中最小的那个。
2. 使用分治，把 k 个链表两两合并，逐层减少链表数量。

这题最关键的观察是：

每个链表都是升序的，所以每次只需要从各个链表的当前头节点中选出最小节点，就能保证合并结果仍然升序。

解法一：优先队列

优先队列中维护所有链表当前还没有合并的头节点。

因为要每次取最小节点，所以使用小根堆。

在 C++ 中可以定义比较器：

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

初始化时，把每个非空链表的头节点放进堆中：

for (ListNode* head : lists)
{
    if (head != nullptr)
    {
        pq.push(head);
    }
}

然后不断弹出堆顶最小节点，把它接到结果链表后面。

如果这个节点还有下一个节点，就把下一个节点放进堆中。

这样堆里始终保存每个链表当前最小的候选节点。

为什么优先队列能保证升序

每个链表本身都是升序的。

对于每条链表来说，当前头节点一定是这条链表剩余节点中最小的。

因此，所有链表剩余节点中的最小值，一定在这些当前头节点里面。

优先队列每次弹出当前头节点中的最小值。

所以每次接入结果链表的节点，都是所有未合并节点中的最小值。

这样从前到后接出来的链表一定是升序的。

解法二：分治合并

分治合并的思路是把 k 个链表拆成两半。

先分别合并左半部分和右半部分，再合并这两个结果。

例如：

[L1, L2, L3, L4]

可以先合并：

L1 + L2
L3 + L4

再合并上面两个结果。

这和归并排序很像。

每一层都会把链表数量减半。

最终只剩下一个完整的升序链表。

为什么分治比顺序合并更均衡

如果顺序合并，可能出现这种情况：

(((L1 + L2) + L3) + L4) + ...

前面合并出来的结果会越来越长，后面不断重复扫描这个长链表。

分治合并则是尽量让长度相近的链表先合并。

每个节点在每一层最多参与一次合并。

一共有大约 log k 层。

所以总时间复杂度是 O(N log k)。

其中 N 是所有链表节点的总数。

边界情况

如果 lists 为空：

lists = []

没有任何链表可以合并，返回 nullptr。

如果 lists 中只有一个空链表：

lists = [[]]

它的头节点是 nullptr，合并结果仍然是空链表。

如果某些链表为空，优先队列解法会跳过空头节点。

分治解法中，空链表也可以正常参与 mergeTwoLists，不会影响结果。

如果 lists 中只有一个链表，分治解法会直接返回这个链表，优先队列解法也会按原顺序依次弹出节点，结果不变。

正确性证明

我们证明：两个解法都能返回包含所有节点且升序排列的链表。

结论 1：优先队列每次弹出的节点是所有未合并节点中的最小节点

每个链表都是升序的。

所以每条链表当前头节点，是这条链表剩余节点中的最小节点。

所有未合并节点中的最小节点，一定是某条链表的当前头节点。

优先队列保存的正是这些当前头节点，并且堆顶是其中最小的节点。

因此每次弹出的节点都是所有未合并节点中的最小节点。

结论 2：优先队列解法生成的链表是升序的

根据结论 1，每次接入结果链表的节点都是当前所有未合并节点中的最小节点。

下一次弹出的节点不会小于已经接入的节点。

所以结果链表从头到尾保持升序。

同时，每弹出一个节点后，如果它还有后继节点，算法会把后继节点加入堆。

因此所有节点都会被加入结果链表，且不会重复加入。

结论 3：mergeTwoLists 能正确合并两个升序链表

合并两个链表时，每次比较两个链表当前头节点。

较小的节点一定是两个链表所有未处理节点中的最小值。

把它接到结果链表末尾，不会破坏升序。

当某个链表为空时，另一个链表剩余部分本身已经有序，可以直接接到末尾。

因此 mergeTwoLists 能正确合并两个升序链表。

结论 4：分治合并能正确合并所有链表

当区间中只有一个链表时，返回它本身，显然正确。

当区间中有多个链表时，算法先递归合并左半部分和右半部分。

根据递归假设，左右两部分都能被合并成升序链表。

再根据结论 3，把这两个升序链表合并后，得到的就是当前区间内所有链表节点组成的升序链表。

因此分治合并正确。

得出结论

由结论 1 和结论 2 可知，优先队列解法正确。

由结论 3 和结论 4 可知，分治合并解法正确。

因此两个解法都能正确合并 k 个升序链表。

举例理解

以：

lists = [[1,4,5],[1,3,4],[2,6]]

为例。

优先队列初始放入三个头节点：

1, 1, 2

每次弹出最小值并接到结果中：

最终得到：

[1,1,2,3,4,4,5,6]

复杂度分析

设所有链表节点总数为 N，链表数量为 k。

解法一

优先队列中最多同时存放 k 个节点。

每个节点入堆、出堆各一次。

• 时间复杂度：O(N log k)
• 空间复杂度：O(k)

解法二

分治合并一共有大约 log k 层。

每一层所有节点都会被合并一次。

• 时间复杂度：O(N log k)
• 空间复杂度：O(log k)

空间复杂度来自递归调用栈。

如果更重视代码直观性，优先队列解法更容易理解。
如果想复用“合并两个有序链表”的逻辑，分治合并也很自然。