CS-Notes 剑指 Offer 第 6 题精讲：从尾到头打印链表的递归、头插法与栈三种实现

在 CS-Notes 的 剑指 Offer 题解 中，链表专题的第一题就是"从尾到头打印链表"：给定一个链表，要求逆序打印出每个结点的值。这道题的考点看似简单——"把顺序倒过来"，但它恰好覆盖了三种最典型的结构化手段：递归的调用栈、头插法改变指针关系、以及栈的后进先出。读完后你将掌握三种方案的完整 Java 实现、各自的复杂度边界（尤其是递归在长链表下的栈溢出风险），并能把它与第 24 题"反转链表"的头插法联系起来，形成对链表指针操作的系统理解。

题目描述

输入一个链表的头结点，从尾到头反过来返回每个结点的值（用 ArrayList 形式返回）。

以链表 1 -> 2 -> 3 为例，期望的返回结果是 [3, 2, 1]。

原链表结构如下：

需要特别注意一个边界情况：如果传入的 listNode 为 null（空链表），三种实现都必须返回一个空列表而不是抛出异常。下文给出的代码全部显式处理了这一点。

方案一：递归

核心思想

要逆序打印链表 1 -> 2 -> 3（结果为 3, 2, 1），可以先逆序打印剩下的子链表 2 -> 3（得到 3, 2），最后再把第一个节点 1 追加到结果末尾。

关键观察在于：2 -> 3 本身也是一个合法的链表，求解它的方式与求解原链表完全相同——"用同一个函数去解一个规模更小的同类问题"，这就是递归。

代码实现

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (listNode != null) {
        ret.addAll(printListFromTailToHead(listNode.next)); // 先递归处理剩余部分
        ret.add(listNode.val);                              // 回溯时再把自己加进去
    }
    return ret;
}

为什么结果是逆序的：从"前序遍历"变成"后序遍历"

这个写法在结构上就是二叉树的"前序遍历改后序遍历"：把当前节点的处理动作（ret.add(listNode.val)）放到递归调用（printListFromTailToHead(listNode.next)）之后执行。

以链表 1 -> 2 -> 3 手动展开递归过程：

1. f(1) 先调用 f(2)；
2. f(2) 先调用 f(3)；
3. f(3) 中 listNode.next == null，递归到底，f(3) 先执行递归分支（返回空表），再执行 add(3)，返回 [3]；
4. 回到 f(2)，把子结果 [3] 加进自己的表，再 add(2)，返回 [3, 2]；
5. 回到 f(1)，最终返回 [3, 2, 1]。

也就是说，Java 的方法调用栈天然充当了一个"后进先出"的容器：越靠后的节点越先被加入结果。

复杂度与局限

• 时间复杂度 O(n)：每个结点恰好访问一次；
• 空间复杂度 O(n)：每个结点占一个调用栈帧，外加结果列表。

必须指出的工程风险是：递归深度等于链表长度。当链表非常长（例如百万级节点）时，递归方案会抛出 StackOverflowError。因此在面试中若面试官追问"链表很长怎么办"，应主动切换到下面两种迭代方案。

方案二：头插法

核心思想

头插法顾名思义是将节点插入到新链表的头部。遍历原始链表时，把当前节点逐个摘下来插到结果链表的最前面，最后结果链表的方向就是反的。

链表的操作核心是维护后继关系。例如要在某个节点 node1 之后插入一个节点 node2，需要修改后继指针：

node3 = node1.next;   // 先记住 node1 原来的后继
node2.next = node3;   // 新节点指向原后继
node1.next = node2;   // node1 改指新节点

头结点的引入

为了能把节点插入"头部"，引入一个不存值的辅助节点——头结点（dummy head）。它只是插入操作的锚点。不要将头结点与第一个节点混为一谈：头结点不存储业务数据，而第一个节点是链表中第一个真正存储值的节点。

代码实现

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    // 头插法构建逆序链表
    ListNode head = new ListNode(-1);   // 头结点，不存值，仅为插入提供锚点
    while (listNode != null) {
        ListNode memo = listNode.next;  // 记住剩余部分，防止断链
        listNode.next = head.next;      // 当前节点指向结果链表的原首节点
        head.next = listNode;           // 头结点改指当前节点
        listNode = memo;                // 前进到剩余链表的下一个节点
    }
    // 构建 ArrayList
    ArrayList<Integer> ret = new ArrayList<>();
    head = head.next;
    while (head != null) {
        ret.add(head.val);
        head = head.next;
    }
    return ret;
}

逐步走一遍

设输入链表为 1 -> 2 -> 3，头结点记为 H，每轮循环后结果链表的变化：

轮次	摘下的节点	结果链表（H 之后）
初始	-	H -> null
1	1	H -> 1
2	2	H -> 2 -> 1
3	3	H -> 3 -> 2 -> 1

最后从 H.next 开始顺序读取即得 [3, 2, 1]。其中 memo 变量是断链保护：不先保存 listNode.next，就永远失去了对剩余链表的引用。

复杂度与注意点

• 时间复杂度 O(n)：第一次遍历做头插 O(n)，第二次遍历读取结果 O(n)；
• 空间复杂度 O(n)：仅结果列表，没有额外调用栈，长链表下比递归安全。

一个实现细节值得留意：头插法过程中会改写原链表的 next 指针，即函数执行后输入链表已被反转。如果题目要求保留原链表（本道题牛客网/LeetCode 的判定并不要求），可以在摘节点时只操作 val 或用新节点复制；面试中被问到这一点，说明你对指针操作的副作用有清醒认识。

方案三：栈

核心思想

栈具有后进先出的特点。遍历链表时把每个结点的值按顺序压栈，最后依次出栈，出栈顺序天然就是逆序——这是把"逆序"问题最直白地转化为"栈序"。

代码实现

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    while (listNode != null) {
        stack.add(listNode.val);
        listNode = listNode.next;
    }
    ArrayList<Integer> ret = new ArrayList<>();
    while (!stack.isEmpty())
        ret.add(stack.pop());
    return ret;
}

栈方案不修改任何链表指针、不产生递归调用，代码意图最清晰，时间复杂度 O(n)，空间复杂度 O(n)（栈 + 结果列表）。

三种方案对比

方案	时间复杂度	空间复杂度	是否修改原链表指针	长链表下的风险
递归	O(n)	O(n) 调用栈 + 结果列表	否	深度过大时栈溢出
头插法	O(n)	O(n) 结果列表	是（原链表被反转）	无
栈	O(n)	O(n) 栈 + 结果列表	否	无

从源码结构看，这三种思路在 CS-Notes 中并不是孤立的：头插法的指针操作与 24. 反转链表 的迭代解法（head.next = newList.next; newList.next = head;）完全同构——本题的头插法过程实际上就是"反转链表"的前半段，只是结果被收集进了 ArrayList；而"利用栈反转顺序"的思想与 9. 用两个栈实现队列 中"in 栈反转一次、out 栈再反转一次"的用法同源，双栈两次反转恰好恢复 FIFO 顺序，单栈一次反转则得到逆序。掌握这三者之间的联系，链表与栈类题目之间可以互相迁移。

选型建议

• 写笔试代码求最短：递归，但要意识到栈溢出边界；
• 面试白板求稳健：栈方案，不碰指针、无副作用；
• 展示指针操作功底：头插法，并能顺势讲出它与反转链表、头结点技巧的关联。

无论选哪种，判空前必须处理 listNode == null 的空链表输入——这是三个实现中共有的边界条件，也是测试用例中最容易遗漏的一条。