0021. Merge Two Sorted Lists
============================
题目信息
--------
:题号: 0021. 合并两个有序链表
:难度: Easy
:主题: 链表、排序、归并、递归、双指针
:原题: `LeetCode 0021 `_
:重点: 从收集全部节点重新排序,推导到只比较两个有序后缀的表头,并用尾指针原地完成两路归并
题目重述
--------
给定两个按非递减顺序排列的单链表 ``list1`` 和 ``list2``,把两条链表中的全部节点合并为一条同样按非递减
顺序排列的链表,并返回结果头节点。
两条输入链表都可能为空。结果必须保留所有节点,值相同的不同节点不能被合并或丢弃。题目允许修改原节点的
``next`` 指针,因此可以直接复用输入节点,不需要为每个值创建新节点。两个当前节点值相等时,先接入任意一个
都不影响结果合法性。
链表节点总数位于 ``[0, 100]``,节点值位于 ``[-100, 100]``。
自建示例
--------
* 交错取值:``list1 = [1, 4, 7]``、``list2 = [2, 3, 8]``,返回 ``[1, 2, 3, 4, 7, 8]``;
* 包含重复值:``list1 = [1, 2, 2]``、``list2 = [1, 2, 5]``,返回 ``[1, 1, 2, 2, 2, 5]``;
* 两侧长度不同:``list1 = [-4, 6]``、``list2 = [-3, 0, 2, 9]``,返回 ``[-4, -3, 0, 2, 6, 9]``;
* 一条链表为空:``list1 = []``、``list2 = [-3, 0, 6]``,返回原第二条链表;
* 两条链表都为空:``list1 = []``、``list2 = []``,返回空链表。
C++ 实现
--------
.. code-block:: cpp
#include
#include
// LeetCode 提供 ListNode 定义。
class Solution {
private:
ListNode* collectAndSort(ListNode* first, ListNode* second) {
std::vector nodes;
for (ListNode* node = first; node != nullptr; node = node->next) {
nodes.push_back(node);
}
for (ListNode* node = second; node != nullptr; node = node->next) {
nodes.push_back(node);
}
if (nodes.empty()) {
return nullptr;
}
std::sort(nodes.begin(), nodes.end(), [](const ListNode* left, const ListNode* right) {
return left->val < right->val;
});
for (int index = 1; index < static_cast(nodes.size()); ++index) {
nodes[index - 1]->next = nodes[index];
}
nodes.back()->next = nullptr;
return nodes.front();
}
ListNode* recursiveMerge(ListNode* first, ListNode* second) {
if (first == nullptr) {
return second;
}
if (second == nullptr) {
return first;
}
if (first->val <= second->val) {
first->next = recursiveMerge(first->next, second);
return first;
}
second->next = recursiveMerge(first, second->next);
return second;
}
ListNode* iterativeMerge(ListNode* first, ListNode* second) {
ListNode dummy;
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;
}
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
return iterativeMerge(list1, list2);
}
};
题解
----
收集后重新排序
~~~~~~~~~~~~~~
暂时不利用两条链表已经有序这一条件,可以先遍历它们,把全部节点指针放入数组,按节点值排序,再按照排序结果
重新设置每个节点的 ``next``。``collectAndSort`` 就是这种直接方法。
它不会遗漏节点:两个遍历把每个输入节点各收集一次,排序只改变指针在数组中的次序,最后按该次序重建一条链。
相同值的节点即使排序后先后次序不确定,也仍是两个独立指针,都会保留在结果中。
设总节点数为 ``N``。收集和重连都是 ``O(N)``,排序需要 ``O(N log N)``,还要保存 ``N`` 个节点指针。
真正的浪费是:两个输入内部的大小关系原本已经全部确定,这种方法却把这些信息丢掉,再对所有节点做一次通用排序。
有序后缀
~~~~~~~~
遍历过程中,``first`` 与 ``second`` 分别指向两条链表尚未处理的后缀。因为每个后缀仍按非递减顺序排列,
后缀最小值必定位于它的表头。
因此,全体未处理节点中的最小值不需要从 ``N`` 个节点中重新搜索,只可能是以下两个候选之一:
* ``first`` 指向的节点;
* ``second`` 指向的节点。
若 ``first->val <= second->val``,则 ``first`` 不大于第二条链表的表头,而第二条链表中的其他节点又都不小于
自己的表头,所以 ``first`` 不大于任何未处理节点,可以安全接入结果。另一种情况完全对称。
接入一个表头后只推进对应指针。被推进链表的剩余部分仍然有序,另一条链表没有变化,于是同样的两个候选模型
在下一轮自动恢复。通用排序因此被替换为一次从左到右的两路归并。
状态演化
~~~~~~~~
以 ``list1 = [1, 4, 7]``、``list2 = [2, 3, 8]`` 为例:
.. list-table::
:header-rows: 1
* - ``first``
- ``second``
- 本轮选择
- 已完成前缀
* - 1
- 2
- 1
- ``1``
* - 4
- 2
- 2
- ``1 -> 2``
* - 4
- 3
- 3
- ``1 -> 2 -> 3``
* - 4
- 8
- 4
- ``1 -> 2 -> 3 -> 4``
* - 7
- 8
- 7
- ``1 -> 2 -> 3 -> 4 -> 7``
* - 空
- 8
- 整体接入第二条后缀
- ``1 -> 2 -> 3 -> 4 -> 7 -> 8``
每次比较只确定结果中的下一个节点,不需要提前知道后续节点的完整交错次序。
递归分解
~~~~~~~~
若两条链表都非空,两个表头中的较小者已经能够确定为当前结果的首节点。假设 ``first`` 较小,则剩余答案是
``first->next`` 与 ``second`` 的合并结果:
.. code-block:: text
first -> merge(first.next, second)
``recursiveMerge`` 直接按照这个定义改写 ``first->next``,并返回 ``first``。若任一链表为空,另一条链表本身
已经有序,可以直接返回,既是递归终点,也是剩余后缀整体接入的情况。
递归每层确定一个结果节点,代码紧贴问题分解。不过相邻层只需要记住“当前选中了哪个节点以及剩余两个表头”,
调用栈最坏仍会为每个节点保存一层状态。算法的选择规则已经足够简单,可以改用显式指针顺序执行。
尾指针归并
~~~~~~~~~~
``iterativeMerge`` 用 ``tail`` 指向已完成结果的最后一个节点。每轮比较两个表头,把较小节点接到
``tail->next``,推进对应输入指针,再让 ``tail`` 移到新接入节点。
循环开始时保持三个事实:
* ``dummy.next`` 到 ``tail`` 是已经确定的非递减结果前缀;
* 该前缀恰好包含两个输入中已经越过的节点,每个节点出现一次;
* ``first`` 与 ``second`` 指向两个尚未处理的有序后缀。
本轮选中的表头是全部未处理节点中的最小值,所以它不会破坏结果前缀的顺序。只推进被选中的输入指针后,已处理
节点和两个未处理后缀仍然互不重叠,循环状态继续成立。
虚拟头节点
~~~~~~~~~~
结果开始时没有真实头节点。若直接维护 ``head`` 与 ``tail``,第一次选中节点时需要同时初始化二者,后续才能
统一使用 ``tail->next``。
虚拟节点 ``dummy`` 预先提供一个固定前驱,使第一次和之后的接入都执行相同操作。它本身不属于结果,最终返回
``dummy.next``。两条输入都为空时,循环不会执行,``dummy.next`` 自然为 ``nullptr``。
剩余后缀
~~~~~~~~
主循环在至少一条链表为空时停止。此时另一条链表的剩余部分本身已经有序。若结果前缀非空,它的表头也不小于
结果尾值;否则它应在上一轮被选择。若结果前缀为空,说明至少一条输入从开始就为空,非空链表可以直接作为结果。
所以只需执行一次 ``tail->next = first != nullptr ? first : second``,把完整后缀接入结果。逐节点继续循环虽然
也能得到正确答案,却会重复执行已经不再需要的空指针判断和尾指针移动。
代码演进
~~~~~~~~
``collectAndSort`` 收集全部节点并重新排序。它不利用输入链表内部已经存在的顺序,需要节点数组、通用排序和完整
重连。
识别出每个未处理后缀的最小值就是表头后,候选集合从全部剩余节点缩减为两个表头。``recursiveMerge`` 删除节点
数组和排序过程,每层只选择一个表头,再递归合并剩余后缀。
``iterativeMerge`` 保留相同的表头选择,使用 ``tail`` 和两个输入指针替代递归调用栈。虚拟头节点又删除了首次
接入的特殊分支;某侧耗尽后,剩余有序后缀通过一次链接整体接入。
公开入口采用 ``iterativeMerge``。它复用输入节点,在保持线性时间的同时只使用常数工作空间。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要代价
* - 收集后排序
- ``O((m+n) log(m+n))``
- ``O(m+n)``
- 保存全部节点指针并进行通用排序
* - 递归归并
- ``O(m+n)``
- ``O(m+n)``
- 每个节点选择一次,空间来自递归调用栈
* - 迭代归并
- ``O(m+n)``
- ``O(1)``
- 每个节点最多作为表头参与一次选择
设两条链表长度分别为 ``m`` 和 ``n``。三种方法都复用原节点,返回链表本身不计入工作空间。迭代方法在一侧
耗尽后直接接入剩余后缀,因此其中部分节点甚至不再需要逐个比较。