面试题6：从尾到头打印链表

从为什么不能直接回头开始

先预测：链表1 → 2 → 3只有next指针，走到3后怎样回到2？节点3没有前驱地址，算法如果没有提前保存2，就无法沿链表本身逆向移动。要从尾到头输出，必须在正向遍历时保存稍后需要的信息。这就是后进先出。

这道“从尾到头打印链表”接收一个单向链表头节点，要求按尾到头顺序输出每个节点值。作者给出两种解法：把节点指针依次压入std::stack后弹出，或先递归访问next、回溯时打印当前节点。两者都利用后进先出。

的遍历方向与输出方向相反。这个矛盾决定至少要付出存储、修改结构或重复遍历中的一种代价，不存在既不存状态、不改链表又只扫描一次的魔法回退。

先定义“打印”的可测试契约

算法题里直接printf很直观，但I/O副作用难以断言，也会把顺序算法与终端格式混在一起。更可测试的接口可以返回值数组，或接受emit(value)回调。真正打印时再把回调连接到日志或输出流。

是本题的默认边界。先反转链表再打印虽然能用O(1)额外空间，但会临时改变next；并发读者、异常中断或提前返回都可能观察到破坏状态。

空链表应产生空输出，不解引用空指针。单节点链表输出该节点一次。默认输入还应是一条以nullptr结束的无环链；若可能有环，普通遍历和递归都不会终止，接口必须先检测环、保存已见集合或设定步数上限。

方法一：显式栈

正向遍历时把每个节点指针压入。到达nullptr后，栈顶是原尾节点；反复弹出便得到尾到头顺序。

#include <stack>
#include <vector>
 
struct ListNode {
    int value;
    const ListNode* next;
};
 
std::vector<int> values_from_tail(const ListNode* head) {
    std::stack<const ListNode*> nodes;
    for (auto node = head; node != nullptr; node = node->next) {
        nodes.push(node);
    }
 
    std::vector<int> result;
    result.reserve(nodes.size());
    while (!nodes.empty()) {
        result.push_back(nodes.top()->value);
        nodes.pop();
    }
    return result;
}

const ListNode*让函数不能通过当前指针修改节点，表达只读意图。它不能阻止其他别名并发修改链表，因此线程安全仍需外部同步或不可变所有权。

时间是O(n)：每个节点入栈、出栈各一次。栈保存n个节点指针，结果也保存n个整数。若接口直接通过回调输出，辅助栈仍是O(n)，但不再额外保存结果数组。

不要简单说显式栈“不会耗尽内存”。std::stack底层容器仍可能分配失败；它的优势是不用为每个节点增加函数调用帧，容量由通用动态存储与分配器管理，失败也可按普通分配异常处理，而不是触发难以恢复的调用栈溢出。

方法二：递归回溯

递归把当前节点、返回地址等状态放进。先处理后继，再输出当前值，就会在返回阶段得到逆序。

#include <functional>
 
void emit_from_tail(
    const ListNode* node,
    const std::function<void(int)>& emit
) {
    if (node == nullptr) {
        return;
    }
    emit_from_tail(node->next, emit);
    emit(node->value);
}

调用emit_from_tail(1)时，1、2、3的栈帧依次建立；遇到nullptr返回后，3先输出，再输出2和1。这是在调用栈上的直接表现。

递归代码短，但空间仍是O(n)，而且调用栈容量通常有限。链表数万或数十万节点时可能栈溢出。C++不保证尾调用优化；这个递归也不是尾递归，因为递归返回后还要执行emit。无法依靠编译器自动把它变成常数栈循环。

为什么默认不反转链表

若允许修改，反转next后正向输出可把额外空间降为O(1)；为了保持调用后结构，还要再反转回来。但“两次反转”不是无副作用：第一次反转后到恢复前，链表处于相反结构。输出回调抛异常、进程取消或另一个线程读取，恢复可能不发生或观察到中间状态。

可以用RAII守卫尽量保证离开作用域时恢复，但析构期异常、并发可见性和节点所有权仍复杂。题目没有授权修改时，显式栈更符合契约。空间限制和只读限制发生冲突时，应向面试官澄清优先级，而不是偷偷违反一项。

不修改且只用O(1)额外空间的另一方案是重复扫描：先数出长度，再为第n-1、n-2等位置每次从头走。它能输出正确结果，但时间为O(n²)，通常不如O(n)时间、O(n)空间的栈。

有环输入必须单独处理

原书链表由nullptr终止，作者测试没有环。若输入可能来自不可信组装，环会让显式栈无限压入，让递归无限深入。不能等内存耗尽来“检测”。

可先用快慢指针O(n)时间、O(1)空间判断有环；发现环后返回错误，因为“尾节点”不存在，“从尾到头”语义也不成立。若业务要对环上有限节点输出，需要重新定义起点、终点和去重顺序，已经是另一道题。

保存已见节点集合也能在遍历时发现环，但增加O(n)空间。显式栈本来就需要线性空间时，可以用同一遍历维护集合；是否值得取决于输入契约。可信内部链表不必每次支付防御成本，但边界层应验证结构。

输出失败与所有权边界

作者直接调用printf，通常忽略输出失败。使用回调或流时，写入可能抛异常或返回错误。显式栈已经完整读取链表，输出失败不会修改链表；调用者可以记录已输出数量或整体重试。递归在回溯中输出，失败会中断剩余前驱值，同样要定义部分输出语义。

栈保存节点指针意味着这些节点在整个收集和弹出阶段必须存活。若另一个所有者可以删除节点，指针会悬空。更安全的方式是保存值副本，或在函数期间持有链表所有权/读锁。保存值会改变元素复制成本，但解除后续对节点生命周期的依赖。

若节点值很大或不可复制，保存指针更高效；这时必须明确链表不可变且生命周期覆盖函数。算法复杂度只写“O(n)个指针”还不够，资源与并发契约同样属于工程正确性。

官方测试与可验证实现

保存节点还是保存值

作者把ListNode*压入栈，弹出时再读取节点值。这样每个栈元素只是一个指针，适合节点值较大或不可复制的情况；代价是整个输出阶段都依赖节点仍然存活、内容没有被并发修改。若链表由另一个线程或所有者管理，悬空指针和数据竞争会破坏结果。

把整数值直接压栈则建立快照。遍历结束后，即使原链表销毁，栈中值仍可安全输出；对本题的int代价很小。若值是大对象，可以保存引用计数句柄、移动到独立快照，或在持有读锁期间完成输出。选择依据不是固定模板，而是值复制成本与生命周期契约。

无论保存哪一种，都必须不改变链表结构：不重写next、不替换头节点，也不借“打印后恢复”绕过只读限制。测试应记录每个节点的后继地址，调用后逐一比较，而不只是比较正向值序列；值相同的重复节点会让只比较内容漏掉链接变化。

输出回调还可能重入算法或抛异常。显式栈已经完成收集，异常只中断弹出；链表本身不变。递归回溯输出时，异常会沿调用栈传播并跳过剩余前驱节点。接口应说明是否允许部分输出，或先收集完整结果再一次性交给调用方，以获得更清晰的失败边界。

如果要多次从尾到头遍历同一条不变链表，每次重建栈都是O(n)。可以缓存反向索引或直接选择双向链表，但这会增加结构存储和更新成本。单次面试题不需要预处理；工程设计则要把查询频率、更新频率和内存一起比较。

最后，所谓“打印”不一定是标准输出。网络发送、文件写入和UI渲染都可能慢或阻塞。核心算法返回迭代结果或值数组，让上层决定批量、背压、取消与错误处理；这样数据结构遍历不承担设备策略，也更容易基准测试。

作者测试三种输入：1→2→3→4→5、单节点1、空链表，并对每个输入分别调用显式栈和递归版本。现代测试应比较返回序列，并在调用后再次正向遍历确认结构未变。

#include <cassert>
#include <vector>
 
void test_reverse_values() {
    const ListNode n5{5, nullptr};
    const ListNode n4{4, &n5};
    const ListNode n3{3, &n4};
    const ListNode n2{2, &n3};
    const ListNode n1{1, &n2};
 
    assert((values_from_tail(&n1) ==
            std::vector<int>{5, 4, 3, 2, 1}));
    assert(n1.next == &n2 && n2.next == &n3);
 
    const ListNode only{1, nullptr};
    assert((values_from_tail(&only) == std::vector<int>{1}));
    assert(values_from_tail(nullptr).empty());
}

长链表测试不应调用递归版本去“看看会不会崩”，而应按配置阈值选择显式栈，或让递归接口明确只接受受限长度。栈溢出往往无法像普通异常一样可靠恢复。

本章练习

本章回顾

1. 单向链表只能沿next正向遍历，逆序输出需要记住已访问节点。
2. 显式栈先压入节点再弹出，时间O(n)、辅助空间O(n)。
3. 递归先访问后继、回溯时输出，调用栈同样占O(n)空间。
4. 深链表可能耗尽调用栈，显式容器更容易控制，但也可能分配失败。
5. 反转再恢复能用常数额外空间，却违反默认只读契约并暴露中间状态。
6. 空链表输出空结果，单节点输出一次；有环链表没有尾节点，需拒绝或另定语义。
7. 返回值数组或输出回调比硬编码printf更容易测试和处理失败。
8. 保存节点指针时必须保证生命周期与并发稳定，保存值则承担复制成本。

名词解释