面试题24：反转链表

从“先改next会失去什么”开始

先预测：链表 1→2→3 中，current指向1。若第一步直接执行 current->next=previous，而 previous 为空，之后怎样找到节点2？原来通向2的唯一链接已经被覆盖；如果没有其他变量保存它，2和3形成的后缀将不可达。

所以反转链表不是把箭头“一起翻面”，而是逐节点迁移。每轮都要先保存下一个节点，再把当前next反向，最后推进处理位置。原书核心短语“前驱、当前与后继指针”对应三个职责，顺序不能交换。

把 previous 指向的部分称为，把 current 及其后面仍维持原方向的部分称为。算法每轮从后缀头取一个节点，放到反转前缀头。

四条语句为什么必须按这个顺序

一轮更新依次是：

1. next=current->next，保存未处理后缀剩余入口。
2. current->next=previous，把当前节点接到已反转前缀前面。
3. previous=current，让previous成为扩大后前缀的新头。
4. current=next，恢复并进入尚未处理的后缀。

第一步叫。若省略，剩余节点并非立即释放，而是失去所有可达路径，最终造成逻辑丢失和内存泄漏。若先推进 current 再改链，又会失去需要修改的旧当前节点。

每轮结束时，previous前缀已反转且尾部指向空，current仍是未处理后缀入口。两个部分覆盖原链表全部节点且互不重叠。current最终为空时，未处理后缀为空，previous就覆盖全部节点。

忠实实现作者的迭代版本

作者维护 pReversedHead、pNode、pPrev。每轮先取得 pNext；当 pNext 为空时，当前节点是原尾，作者把它记录为。随后再反向链接并推进。

struct ListNode {
    int value;
    ListNode* next = nullptr;
};
 
ListNode* reverseList(ListNode* head) {
    ListNode* reversedHead = nullptr;
    ListNode* current = head;
    ListNode* previous = nullptr;
 
    while (current != nullptr) {
        ListNode* next = current->next;
 
        if (next == nullptr) {
            reversedHead = current;
        }
 
        current->next = previous;
        previous = current;
        current = next;
    }
    return reversedHead;
}

空链表时循环零次，reversedHead保持空；单节点时 next立即为空，该节点同时被记录为新头，并把它的next设为previous即空；多节点时只有原尾满足 next为空。三类输入无需额外分支。

更常见的简化版直接在循环结束时返回 previous，因为它同样指向原尾。作者显式记录 reversedHead 的写法把“在哪一刻识别新头”展示出来。重构原书时应保留这层含义，再说明两种实现等价。

原书要求函数“返回新的头节点”。调用者必须用返回值替换旧head；若忽略返回值，旧head现在是尾节点且next为空，看起来链表只剩一个节点，实际其余节点仍由新头可达。

正确性来自前缀与后缀不变量

初始 previous为空，可视为长度0的正确反转前缀；current=head，未处理后缀是完整原链。不变量成立。

假设一轮开始不变量成立。next保存后缀除current外的入口；current指向previous后，扩大后的前缀顺序恰为原已处理节点的逆序；previous和current推进后，剩余后缀仍保持原方向。节点没有丢失或重复，不变量恢复。

循环结束 current为空，所有原节点都在previous前缀中，且next方向与原顺序完全相反。原头最先被处理，它的next被设为空，成为新尾；原尾最后被处理，成为新头。因此返回reversedHead正确。

时间、空间与节点身份

current依次访问每个节点一次，每轮做常数次指针赋值，时间 O(n)。只使用三个工作指针和一个结果指针，额外空间 O(1)。算法没有分配、复制或释放节点，只改变next。

这种操作称为。所有节点地址和value保持不变，但由head可达的顺序改变。外部持有某节点指针仍指向同一对象，不过它看到的next已经不同。

返回值不转移节点所有权，它只是新的借用入口。若链表由容器拥有，容器必须更新内部head；若调用者继续让旧head承担销毁入口，只会释放原头一个节点并泄漏其余节点。

递归版本如何对照

递归可以先反转 head->next 后缀，再让原后继的next指回head，并把head->next设为空。它更接近数学归纳，却需要每个节点一层调用栈：

ListNode* reverseRecursive(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
 
    ListNode* newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

head->next=nullptr不能省略。回溯前原来有 head→successor，回溯中又建立 successor→head；不切断旧边就形成二节点环。递归时间仍为 O(n)，但调用栈 O(n)，超长链表可能栈溢出。

作者源码只实现迭代版，递归应作为理解和比较，不应替换原书主答案。生产环境通常优先迭代：空间边界清晰，也不会受语言递归深度限制。

环、共享尾和并发是输入契约

算法假设链表无环。若有环，current永远不会为空；更危险的是逐步改链后结构变化，可能提前回到已处理节点，结果不可定义。处理不可信结构前应先判圈，或由容器类型保证无环。

若两条链共享尾部，反转其中一条会修改共享节点next，从而破坏另一条链。唯一所有权链表不会共享节点；裸指针API必须把“调用者拥有整条独占无环链”写进前置条件。

并发读者可能观察到链表被分成两个暂时部分，或看到部分箭头已反向。反转不是原子操作，必须在独占锁下完成，或构造新不可变链后原子发布新头。只把head设为原子变量不能保护内部next修改。

如果节点析构或移动会抛异常，本算法不触碰value也不销毁节点，因此指针赋值本身通常无异常。自定义智能指针或写屏障可能改变这一点；需要事务语义时，应先确认链接赋值保证。

部分反转与双向链表扩展

只反转位置 m 到 n 时，需要保存三条边界：区间前驱、原区间头和区间后继。区间内部仍使用同一三指针循环，完成后让前驱连到区间新头，让原区间头连到后继。哨兵节点可统一m=1边界。

反转双向链表时，每个节点的next与prev都要交换，遍历方向也要改为交换后的prev即原next。最后原尾成为新头。只改next会让prev不变量失效，后向遍历得到旧结构。

持久化不可变链表不能原地改next。可从原头遍历，每次创建新节点并让它指向已构造前缀，自然得到逆序副本；时间 O(n)、新节点空间 O(n)，原链仍可共享给读者。

作者三组测试与增强断言

Test1 构造1到5并打印反转前后；Test2测试单节点；Test3传空。打印能演示结果，但自动验收应检查返回地址、完整值序列、原头成为尾、每个原节点恰好出现一次。

双重反转是有力的变形性质：对无环链表反转两次，应恢复原head、原next关系和地址顺序。它不能替代单次期望断言，因为某些对称错误可能两次后恢复，但能发现节点丢失和错误成环。

#include <array>
#include <cassert>
 
void testReverseList() {
    ListNode n5{5, nullptr};
    ListNode n4{4, &n5};
    ListNode n3{3, &n4};
    ListNode n2{2, &n3};
    ListNode n1{1, &n2};
 
    ListNode* reversed = reverseList(&n1);
    const std::array<ListNode*, 5> expected{
        &n5, &n4, &n3, &n2, &n1
    };
    ListNode* cursor = reversed;
    for (ListNode* node : expected) {
        assert(cursor == node);
        cursor = cursor->next;
    }
    assert(cursor == nullptr);
    assert(n1.next == nullptr);
 
    assert(reverseList(reversed) == &n1);
 
    ListNode only{9, nullptr};
    assert(reverseList(&only) == &only);
    assert(reverseList(nullptr) == nullptr);
}

地址数组比只比较1到5的值更严格：即使实现交换了value而没有反转节点，也会被发现。遍历最终必须到空；可增加最多n步的保护，避免错误成环让测试挂死。

使用堆节点时，应从反转后的新头统一销毁。测试若仍从旧头DestroyList，只会释放新尾；正确的夹具生命周期也是算法契约的一部分。

工程接口如何表达副作用

reverseList会修改传入链表，名称和类型应清楚表达可变操作。只接收 const ListNode* 的函数不能合法反转；强制const_cast会违背调用者只读承诺。

可让容器成员函数 reverse 返回void并内部更新head，减少调用者忽略返回值的风险；自由函数则返回新头，适合算法题和裸链。若失败不可能发生，不必返回状态与新头二元组。

在调试构建中可先检测环并统计节点数，反转后再验证长度、多重集合和无环；生产构建若容器已维护不变量，可省去额外遍历。检查层级应与输入可信度匹配。

正确性与复杂度收束

循环每轮把一个节点从未处理后缀转移到已反转前缀，后缀长度严格减一，所以有限无环链表必终止。后继暂存保证转移前后两段入口都可达，重写next保证新前缀顺序正确。

终止时后缀为空，前缀包含所有且仅有原节点。原尾成为前缀头、原头next为空，故结果是原顺序的精确逆序。每节点常数操作，总时间O(n)、额外空间O(1)。

本章练习

本章回顾

1. 反转链表必须使用前驱、当前与后继指针分工。
2. 每轮先保存下一个节点，再把current->next改为previous。
3. previous是已反转前缀入口，current是未处理后缀入口。
4. 作者在pNext为空时记录原尾，并返回新的头节点。
5. 原头第一轮指向空，最终成为新尾，避免形成环。
6. 迭代时间O(n)、额外空间O(1)，递归另需O(n)调用栈。
7. 输入应是独占、无环、遍历期间不变的链表。
8. 测试应比较节点地址、完整序列、新尾为空和双重反转。

名词解释