0023. Merge k Sorted Lists ========================== 题目信息 -------- :题号: 0023. 合并 K 个升序链表 :难度: Hard :主题: 链表、归并、分治、优先队列 :原题: `LeetCode 0023 `_ :重点: 将两路归并扩展到多路归并,并控制每个节点参与比较的次数 题目重述 -------- 给定一个链表数组 ``lists``,其中每条单链表都按节点值非递减排列。把所有链表中的节点合并为一条非递减链表, 返回合并后的头节点。 输入数组可以为空,数组中的任意链表也可以为空。``lists`` 的长度位于 ``[0, 10^4]``,所有链表的节点总数 不超过 ``10^4``,节点值位于 ``[-10^4, 10^4]``。结果应保留所有节点,包括值相同的不同节点;可以重新连接 原节点,无需创建对应的新节点。 自建示例 -------- * 一般情况:``lists = [[1, 4, 7], [2, 5], [3, 6, 9]]``,返回 ``[1, 2, 3, 4, 5, 6, 7, 9]``; * 包含空链表:``lists = [[], [-2, 3, 3], [0, 3]]``,返回 ``[-2, 0, 3, 3, 3]``; * 输入数组为空:``lists = []``,返回空链表; * 所有链表均为空:``lists = [[], [], []]``,返回空链表; * 只有一条链表:``lists = [[-1, 2, 2]]``,直接返回这条链表。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: struct GreaterNode { bool operator()(const ListNode* left, const ListNode* right) const { return left->val > right->val; } }; ListNode* mergeTwo(ListNode* first, ListNode* second) { ListNode dummy(0); ListNode* tail = &dummy; while (first != nullptr && second != nullptr) { if (first->val <= second->val) { tail->next = first; first = first->next; } else { tail->next = second; second = second->next; } tail = tail->next; } tail->next = first != nullptr ? first : second; return dummy.next; } ListNode* mergeSequentially(const std::vector& lists) { ListNode* merged = nullptr; for (ListNode* head : lists) { merged = mergeTwo(merged, head); } return merged; } ListNode* mergeByIntervals(std::vector lists) { const int count = static_cast(lists.size()); if (count == 0) { return nullptr; } for (int interval = 1; interval < count; interval *= 2) { for (int start = 0; start + interval < count; start += 2 * interval) { lists[start] = mergeTwo(lists[start], lists[start + interval]); } } return lists[0]; } ListNode* mergeWithHeap(const std::vector& lists) { std::priority_queue, GreaterNode> candidates; for (ListNode* head : lists) { if (head != nullptr) { candidates.push(head); } } ListNode dummy(0); ListNode* tail = &dummy; while (!candidates.empty()) { ListNode* node = candidates.top(); candidates.pop(); ListNode* next = node->next; tail->next = node; tail = node; if (next != nullptr) { candidates.push(next); } } tail->next = nullptr; return dummy.next; } public: ListNode* mergeKLists(std::vector& lists) { return mergeByIntervals(lists); } }; 题解 ---- 两路归并 ~~~~~~~~ 任意一条有序链表的最小未处理节点都在当前表头。合并两条链表时,全局最小未处理节点只能是两个表头中较小的 一个;把它接入结果并推进对应指针后,剩余问题仍是两条有序链表的归并。 ``mergeTwo`` 复用输入节点,每轮恰好消耗一个表头。某条链表耗尽后,另一条剩余部分已经有序,并且其中所有值 都不小于已接入结果的最后一个值,所以可以整体连接。若两条链表共有 ``x`` 个节点,该操作耗时 ``O(x)``。 顺序归并的失衡 ~~~~~~~~~~~~~~ 最直接的多路扩展是先合并第 0、1 条链表,再把结果与第 2 条合并,依次处理全部链表。``mergeSequentially`` 始终得到正确结果,但早期进入结果的节点会在以后每次归并中被重新扫描。 假设 ``k`` 条链表长度接近,节点总数为 ``N``。第 ``i`` 次归并要扫描前 ``i`` 条链表积累出的长结果,总代价 近似为: .. math:: \frac{N}{k}(1+2+\cdots+k)=O(Nk) 两路归并本身已经是线性操作,退化来自归并树失衡:一个不断增长的长链表反复与短链表合并。要减少重复扫描, 需要让规模相近的结果优先合并。 平衡归并树 ~~~~~~~~~~ ``mergeByIntervals`` 先合并相邻的单条链表,再合并相邻的两条链表结果,之后合并四条、八条,直到只剩一个 结果。``interval`` 表示当前每个已归并分组覆盖的原链表数量。 在同一层中,各次两路归并处理的节点集合互不重叠,所以这一层总共只扫描 ``N`` 个节点。每经过一层,分组规模 至少翻倍,因此最多有 ``ceil(log2 k)`` 层。每个节点每层至多参与一次归并,总时间为 ``O(N log k)``。 不能配成一对的尾部分组会留到下一层。它已经有序,之后再与相邻分组归并即可,因此 ``k`` 不是二的幂也不会 遗漏任何链表。每条原链表最终沿归并树进入根节点,所有输入节点都被保留一次;每次两路归并又保持非递减顺序, 所以根节点对应的链表就是完整有序结果。 公开入口采用这一方法。它直接复用第 21 题的两路归并,并重新连接原节点。 最小堆候选集 ~~~~~~~~~~~~ 多路归并也可以直接决定结果的下一个节点。每条未耗尽链表的最小节点仍是其表头,所以全局最小未处理节点一定在 这些表头之中。``mergeWithHeap`` 把每条非空链表的当前表头放入最小堆,堆顶就是下一项。 弹出某条链表的表头后,它的后继才成为该链表新的最小未处理节点,因此只需把这个后继加入堆。循环过程中,每条 未耗尽链表在堆中恰有一个代表: * 不需要放入更深节点,因为它们不小于本链表当前表头; * 不能缺少当前表头,否则该链表的最小值可能被遗漏; * 堆顶不大于所有链表代表,也就不大于任何未处理节点。 因此每次弹出的节点都可以安全接在结果尾部。相同值的节点仍是不同指针,会分别入堆和出堆,不会被去重。 两种平衡策略 ~~~~~~~~~~~~ 分治与最小堆都把单个节点的比较成本控制在 ``O(log k)`` 级别: * 分治让节点沿平衡归并树逐层向上,每层最多被扫描一次; * 最小堆让节点入堆、出堆各一次,每次堆操作只面对至多 ``k`` 个当前表头。 分治反复调用简单的两路归并,常数较小;最小堆始终显式维护所有链表的当前最小候选。二者都复用原链表节点, 区别在于组织候选的方式,而不是最终复杂度。 复杂度分析 ~~~~~~~~~~ 设 ``N`` 为全部节点数,``k`` 为链表数量。 ``mergeSequentially`` 最坏时间复杂度为 ``O(Nk)``,除调用参数外只使用 ``O(1)`` 指针空间。 ``mergeByIntervals`` 的时间复杂度为 ``O(N log k)``。实现复制了长度为 ``k`` 的头指针数组,工作空间为 ``O(k)``;链表节点本身没有复制。 ``mergeWithHeap`` 中每个节点入堆、出堆各一次,堆大小不超过非空链表数,时间复杂度为 ``O(N log k)``, 工作空间为 ``O(k)``。返回链表复用输入节点,结果本身不计入额外空间。