面试题25：合并两个排序的链表

从“全局最小值只可能在哪”开始

先预测：list1为1→3→5，list2为2→4→6。合并结果的第一个节点需要扫描两条链的全部节点吗？不需要。因为每条链自身升序，任何后续节点都不小于当前头；全局最小剩余节点只可能是head1或head2中较小者。

这就是合并两个排序的链表的局部决策依据。选择较小头后，该节点成为归并节点；未选链保持不动，选中链前进一格，剩余问题仍是两条排序链的合并。

是必要前置条件。若输入1→5→3，头部比较无法发现后面的3应该排在5前面；算法仍会终止，却不能保证输出有序。

作者递归如何缩小同类问题

若head1为空，结果就是head2；若head2为空，结果就是head1。这个无需继续分解、可直接返回的条件称为，也是本题的空链表边界。

两链都非空时，作者比较两个头节点。head1值严格小于head2时选head1，并让它的next指向Merge(head1.next, head2)；否则选head2，并递归合并head1与head2.next。

每层固定一个全局最小剩余节点，待合并总节点数减一。递归返回的后缀已经有序，且其中所有值不小于本层所选头，所以把它接到next后仍整体有序。

忠实实现严格小于的作者版本

作者使用严格小于号。两个值相等时走else，先选择第二条链的节点。这不会破坏值序列有序性，但会决定跨链重复节点的身份顺序。

struct ListNode {
    int value;
    ListNode* next = nullptr;
};
 
ListNode* mergeSortedLists(ListNode* head1, ListNode* head2) {
    if (head1 == nullptr) return head2;
    if (head2 == nullptr) return head1;
 
    ListNode* mergedHead = nullptr;
    if (head1->value < head2->value) {
        mergedHead = head1;
        mergedHead->next =
            mergeSortedLists(head1->next, head2);
    } else {
        mergedHead = head2;
        mergedHead->next =
            mergeSortedLists(head1, head2->next);
    }
    return mergedHead;
}

函数没有创建新业务节点，也没有复制value；它把原节点的next重新连接成一条链，这叫。返回后，两条输入链的原头不再代表彼此独立的旧结构，调用者应把所有权统一转交给合并结果。

重复值的相等策略

把相等时选择哪条链称为。作者的严格小于使第二链优先；非严格小于等于使第一链优先。

两种策略都保持每一条输入链内部的相对顺序，因为任何链的指针都只向前移动。但“稳定合并”若定义为第一输入中的相等节点优先于第二输入，就必须用小于等于；若数据带时间戳、来源优先级或稳定ID，策略需要由接口明确。

只比较输出值无法验证相等策略。作者Test2的两条链都是1→3→5，值结果必为1,1,3,3,5,5；只有保存节点地址或来源标签，才能看出每对相等值是第二链节点先出现。

迭代版保持同一语义

递归或迭代只是控制流不同。迭代版可用栈上哨兵统一第一次接入，并在相等时同样选择head2，保持作者语义：

ListNode* mergeSortedListsIterative(ListNode* head1,
                                    ListNode* head2) {
    ListNode dummy{};
    ListNode* tail = &dummy;
 
    while (head1 != nullptr && head2 != nullptr) {
        if (head1->value < head2->value) {
            tail->next = head1;
            head1 = head1->next;
        } else {
            tail->next = head2;
            head2 = head2->next;
        }
        tail = tail->next;
    }
 
    tail->next = head1 != nullptr ? head1 : head2;
    return dummy.next;
}

每轮只移动被选中节点所属链的头指针，另一链仍停在当前最小节点。tail必须在接入后前进到新尾；若只移动输入指针、不移动tail，下一轮会覆盖同一条next链接，丢失已接入节点。

循环结束时至少一条链为空。另一条链整体已排序，且其头值不小于已合并尾，直接整段连接即可，无需逐节点继续比较。哨兵是局部栈对象，只用其next作为真实结果，不会进入返回链。

递归栈与迭代空间

设两链长度为m和n。每层递归固定一个节点，最深可能达到m+n层，时间O(m+n)，调用栈O(m+n)。长链会触发栈溢出，因此生产代码通常使用迭代版，额外工作空间O(1)。

递归返回阶段虽然在赋值next，但比较和选择发生在向下调用时；每个节点只被选择一次。代码短不等于没有额外空间，调用栈保存每层的所选节点与返回位置。

迭代版使用哨兵、tail和两个输入指针。哨兵不按输入规模增长，所以仍是常数空间。若为了保持输入不变而复制每个节点，空间才变为O(m+n)，那是不同所有权契约。

输入共享、环和别名风险

两条输入链必须无环且不共享节点。若它们在某个尾部交汇，递归会从不同路径遇到同一物理节点，重连可能让节点指向自己或形成环。最极端的head1==head2会在比较相等时反复选择head2并把同一链与自身合并，行为错误。

裸指针接口应声明两条链节点集合互斥。容器使用唯一所有权时，可通过移动两个head进入合并函数自然表达；共享所有权结构若要保留旧链，应创建新节点而不是原地重连。

输入有环时没有空链递归基，算法不终止。并发修改next也会破坏有序性和所有权。调用期间需要独占两条链，或先复制不可变快照。

比较器若抛异常，递归或迭代可能已经重连一部分节点，只能提供基本保证。int比较无异常；泛型版本应说明比较和链接操作的异常语义，强保证通常需要先确定顺序再提交或构造新链。

作者五组测试分别锁定什么

Test1合并1→3→5与2→4→6，验证严格交错选择。Test2合并两条相同的1→3→5，验证重复值和相等分支。Test3合并两个单节点1与2，验证最小非空规模。

Test4让第二条链为空，递归基直接返回第一链；Test5两条都为空，返回空。作者没有单独写第一链为空、第二链非空的测试，但代码第一个递归基覆盖它，增强套件应补上。

自动测试需要同时检查四个性质：值非降、节点总数等于m+n、每个输入地址恰好出现一次、结果最终到空。重复值测试还要检查作者第二链优先：

#include <array>
#include <cassert>
 
void testMergeSortedLists() {
    ListNode a5{5}, a3{3, &a5}, a1{1, &a3};
    ListNode b6{6}, b4{4, &b6}, b2{2, &b4};
 
    ListNode* merged = mergeSortedLists(&a1, &b2);
    const std::array<ListNode*, 6> expected{
        &a1, &b2, &a3, &b4, &a5, &b6
    };
    for (ListNode* node : expected) {
        assert(merged == node);
        merged = merged->next;
    }
    assert(merged == nullptr);
 
    ListNode aEqual{1};
    ListNode bEqual{1};
    merged = mergeSortedLists(&aEqual, &bEqual);
    assert(merged == &bEqual);
    assert(merged->next == &aEqual);
 
    ListNode only{7};
    assert(mergeSortedLists(&only, nullptr) == &only);
    assert(mergeSortedLists(nullptr, nullptr) == nullptr);
}

测试用栈节点避免手工释放，但必须保证结果不活过作用域。堆节点则只能从合并后的唯一head统一销毁，不能再分别Destroy两条输入链，否则会重复释放。

可以随机生成两组已排序值与唯一节点ID，用数组标准归并作为参考，比较值和来源策略。若只对结果调用sort再比较，会掩盖输出本身无序，必须按遍历顺序检查。

有序性与完整性的证明

递归基中一条为空，另一条本身有序，返回正确。两条非空时，较小头不大于任一后续节点，作为结果头正确；递归子问题规模更小且按归纳假设有序，将其接到所选头后整体仍有序。

每层恰好选择一个节点并只前进对应输入链，节点不会丢失或重复；最终某链为空，另一后缀整段接入。结果包含两输入节点多重集合的并集。

递归深度有限，因为每层总剩余节点数减一。迭代版维护同一不变量：dummy.next到tail是已合并有序前缀，head1和head2是两个有序未处理后缀。两种控制流因此语义等价。

从两链推广到k链

在泛型链表中，排序与合并必须使用同一个比较器。若输入按降序排列，却仍用小值优先，结果不会保持原顺序；应改为每次选择更大的头。比较器还要形成稳定的一致次序：如果同一对节点有时返回真、有时返回假，递归选择就无法证明有序。

浮点值中的 NaN 是典型边界。普通小于比较对 NaN 两个方向都为假，作者分支会把它当作“第一头不小于第二头”而选择第二链，却不能建立完整数值次序。业务若允许 NaN，必须定义它排在前、排在后或直接拒绝，并用同一规则预排序输入。

节点保存不可复制资源并不妨碍原地合并，因为算法只改next，不移动value；但两个输入容器的分配器、回收策略和生命周期必须兼容。若节点只能由各自容器释放，把它们串成一个结果会让销毁责任不清，应改为复制值到统一所有者或让返回容器记录来源。

顺序把k条链逐条合并，最坏会让早期节点被反复扫描，总时间接近O(Nk)。更好的分治法成对合并，每个节点经历约log k层，总时间O(N log k)。

最小堆也能维护k个当前头，每次弹出最小节点并压入其后继，时间O(N log k)、额外空间O(k)。重复值来源顺序要放入堆键，例如值、链编号和链内序号，才能得到确定策略。

无论推广方式，核心仍是当前最小候选只在各链头部。理解“两头比较”之后，k路归并只是把两个候选扩成k个候选的数据结构选择。

本章练习

本章回顾

1. 合并两个排序的链表时，全局最小剩余节点只可能在两个头部。
2. 比较两个头节点，选择较小者并递归合并其余后缀。
3. 任一链为空时直接返回另一链，这是递归基和空链表边界。
4. 作者使用严格小于，相等时先选第二条链节点。
5. 递归或迭代都为O(m+n)时间，但递归需要O(m+n)调用栈。
6. 原地重连复用节点，合并后原两链不再是独立结构。
7. 输入必须升序、无环、节点集合互斥且遍历期间不变。
8. 测试应检查有序性、完整地址集合、重复值策略和最终空尾。

名词解释