LeetCode 剑指 Offer 06. 从尾到头打印链表

约 8 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动 阿里巴巴 剑指 Offer 剑指 Offer（第 2 版）
标签
双指针 栈 链表 递归
目录

题目描述

✅ 剑指 Offer 06. 从尾到头打印链表

image-20241107204146295

题意分析

给一条单链表的头节点，要求返回一个数组，把每个节点的值按从尾到头的顺序装进去。返回的是值的数组，不是链表。

矛盾一目了然：要求的输出顺序与唯一可行的遍历顺序完全相反。单链表的每个节点只保存 next，拿不到前驱，因此只能从头往尾走一遍；而答案要的是从尾往头。这道题考的就是如何弥合这个方向差。

还有一个隐含约束：题目返回的是数组，而数组必须一次性确定长度。链表本身不携带长度信息，所以要么先遍历一趟数出节点数，要么借助一个能动态增长的中间结构。这个细节决定了实现上是「两趟」还是「一趟加转存」。

题目明确说明不能修改原链表，这就排除了「先反转链表再顺序读取」这条路——虽然它 $O(1)$ 空间，但破坏了输入。面试中如果给出这个方案，一定要主动说明它会修改入参，并询问是否允许。

节点数上限是 $10^4$，规模很小，任何 $O(n)$ 方案都能轻松通过；递归写法的栈深度一万层在 Java 默认栈大小下也刚好能过，但这个数字已经接近危险区，值得在分析里点一句。

边界只有一个：链表为空，此时应返回长度为 0 的数组而不是 null。

解法：栈维护待匹配状态

核心思路

最先想到的往往是「反转链表再顺序输出」。它的空间是 $O(1)$，但代价是改动了原链表的结构，题目不允许；即便允许，把输入弄脏在工程上也是坏习惯。

第二个想法是「先数出长度 n，再开数组，然后第二趟遍历时把第 i 个节点写到 res[n-1-i]」。它完全正确、空间只有必须的输出数组，是本题事实上的最优解。缺点是要走两趟、还要维护一个倒着走的下标，写起来略绕。

而这里选择的思路是把「顺序反转」这件事交给一个天然具备反转能力的数据结构：栈。它的后进先出语义，正好把「最先压入的头节点」变成「最后弹出」，把「最后压入的尾节点」变成「最先弹出」。

于是分两个阶段。第一阶段从 head 开始顺序遍历，把每个 val 压栈；此阶段维持的不变量是：栈中从底到顶依次是已访问过的节点值，且顺序与链表方向一致。遍历结束时栈里正好是整条链表，栈顶是尾节点的值。

第二阶段不断弹栈，依次写入结果数组；此阶段的不变量是：已弹出的元素恰好是链表末尾若干个节点的值，且按从尾到头的顺序排列在 res 的前缀里。栈空时结果数组填满，正是答案。

栈还顺带解决了长度问题：压栈完成后 stack.size() 就是节点数，可以直接用它开数组，不需要单独数一趟。

这个写法的价值在于它把「方向反转」这个需求和「栈」这个结构直接对应起来，思路一句话就能讲清，是面试中最容易表达的方案。代价是 $O(n)$ 的额外空间，回答时应主动与两趟法做对比。

解题步骤

  • 准备一个栈：Java 用 ArrayDeque 而不是老旧的 Stack——后者继承自 Vector，每个方法都带同步开销。Go 没有内置栈，直接用切片模拟：append 即压栈，从尾部取即弹栈。
  • 从 head 顺序遍历，把每个 head.val 压栈：这一趟是唯一能走的方向。注意这里直接复用形参 head 作游标是安全的，因为全程只读取 next、不修改任何指针，原链表结构保持完好。
  • 循环条件用 head != null：用节点本身而不是 head.next 作条件，才能保证最后一个节点也被压入；空链表则一次都不进，栈保持为空。
  • 用 stack.size() 开结果数组：压栈完成后栈的大小就是链表长度，省掉了单独计数的一趟。空链表时长度为 0，自然得到空数组，无需特判。
  • 循环弹栈并顺序写入 res：res[i++] = stack.pop() 中，第一次弹出的是栈顶即尾节点的值，正好放在结果的第 0 位。Go 的实现等价地用下标 len(stack)-1-i 从后往前读切片，效果相同且省掉了真正的弹出操作。
  • 返回 res：栈空时结果数组恰好填满，两个循环的次数都等于节点数。

以 1 → 3 → 2 走一遍（答案应为 [2, 3, 1]）。

压栈阶段。head 指向 1，压入 1，栈从底到顶是 [1]；head 移到 3，压入 3，栈是 [1, 3]；head 移到 2，压入 2，栈是 [1, 3, 2]；head 变成 null，循环退出。此时栈顶是 2，正是链表的尾节点值。

建数组。stack.size() 为 3，开 res = new int[3]，i = 0。

弹栈阶段。第一次弹出 2（栈顶），res[0] = 2，栈剩 [1, 3]；第二次弹出 3，res[1] = 3，栈剩 [1]；第三次弹出 1，res[2] = 1，栈空。

返回 [2, 3, 1]，正确。可以看到压栈时越靠后的节点越晚入栈、也就越早出栈，「后进先出」恰好完成了方向的翻转。

再看边界 head = null：压栈循环一次不进，栈为空，stack.size() 为 0，res 是长度为 0 的数组，弹栈循环同样不进，直接返回空数组，正确。

代码实现

class Solution {
    // 出栈顺序即为从尾到头的结果。
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();

        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }

        int[] res = new int[stack.size()];
        int i = 0;
        while (!stack.isEmpty()) {
            res[i++] = stack.pop();
        }

        return res;
    }
}

func reversePrint(head *ListNode) []int {
    // 出栈顺序即为从尾到头的结果。
    stack := make([]int, 0)
    for head != nil {
        stack = append(stack, head.Val)
        head = head.Next
    }

    res := make([]int, len(stack))
    for i := 0; i < len(stack); i++ {
        res[i] = stack[len(stack)-1-i]
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是链表节点数。压栈一趟、弹栈一趟，各访问每个元素恰好一次，栈的压入弹出都是均摊 $O(1)$。
  • 空间复杂度：$O(n)$，栈最多同时保存全部 $n$ 个节点值。结果数组同样是 $O(n)$，但它是题目要求的输出不计入额外开销。若改用「先数长度再倒着填」的两趟法，额外空间可以降到 $O(1)$——这是本解法唯一的可优化点，面试时应主动提出。

关键点总结

  • 需求顺序与可行遍历顺序相反时，先想栈。栈的后进先出天然完成一次反转，这个映射关系在逆序输出、括号匹配、表达式求值、单调栈等题里反复出现，是数据结构选型最基本的直觉之一。
  • 栈解法与两趟法的取舍要说清楚：栈是一趟遍历换 $O(n)$ 空间，两趟法是多走一趟换 $O(1)$ 空间。面试时先给栈解法讲清思路，再主动补一句「如果要求常数额外空间，可以先数长度再倒着填」，比只给一种方案强得多。
  • 「反转链表再顺序读」虽然空间最优，但会破坏输入；凡是修改入参的方案都要先向面试官确认是否允许，这是工程素养的体现。
  • 递归也是隐式用栈的写法（先递到底再回溯收集），代码更短，但一万层递归已逼近默认栈容量；能指出「递归深度等于链表长度、存在栈溢出风险」是加分项。
  • 用栈的 size() 同时充当「节点计数」，省掉一趟单独的长度统计——留意一个结构能否顺带提供别的信息，往往能简化代码。

易错点总结

  • 压栈后直接按栈的底到顶顺序读取：Go 里若写成 res[i] = stack[i]，1 → 3 → 2 会返回 [1,3,2]，正好是原顺序，反转完全没有发生。
  • 在压栈前就开好结果数组：链表长度未知，只能猜一个容量，猜小了越界、猜大了尾部残留 0；必须等压栈结束用 stack.size() 来定长。
  • 用 Stack 的 push 却用 poll 取值：Java 的 ArrayDeque 里 push 是往头部插、poll 也是从头部取，两者配对正确；但若改用 addLast 压入再 poll 取出，就变成了队列语义，1 → 3 → 2 会返回 [1,3,2]。压入与弹出必须在同一端。
  • 循环条件写成 head.next != null：最后一个节点不会被压入，1 → 3 → 2 只会返回 [3,1]，结果永远少一个元素；head 为空时还会直接空指针。
  • 弹栈时用 for (int i = 0; i < stack.size(); i++)：size() 随着弹出不断变小，循环在中途就停止，1 → 3 → 2 只会填入前两个位置，返回 [2,3,0]。必须先把长度存进局部变量或改用 while (!stack.isEmpty())。
  • 空链表返回 null：正确答案是长度为 0 的数组，返回 null 会导致判题时空指针。
  • 为省空间而先反转链表：题目不允许修改原链表；即使不看这条约束，1 → 3 → 2 反转后原 head 变成尾节点，调用方持有的引用会指向一条只剩单节点的链，属于污染入参。
  • 用递归但把结果收集写在递归调用之前：dfs(head) 里先 add(head.val) 再 dfs(head.next)，得到的是正序而非逆序；收集动作必须放在递归调用之后的回溯阶段。
  • 递归写法用 List 收集却在每层新建列表：每层的结果无法合并，最终只返回最后一层的单个元素。
  • Java 里把 int 存进 Deque<Integer> 后忘记结果数组是 int[]：res[i++] = stack.pop() 依赖自动拆箱，若栈声明成 Deque<Object> 则编译不过；同时要意识到装箱带来的额外开销，在 $10^4$ 规模下无碍但值得知道。

相似题目

题目 难度 考察点
206. 反转链表 简单 真正改指针反转结构，$O(1)$ 空间，与本题「只反转输出」形成对照
剑指 Offer 24. 反转链表 简单 与 206 同题
LCR 024. 反转链表 简单 与 206 同题
234. 回文链表 简单 同样需要逆序访问，用栈是直观解，进阶要求快慢指针加反转后半段
面试题 02.06. 回文链表 简单 与 234 同题
445. 两数相加 II 中等 高位在前但加法要从低位起，用两个栈同时逆序取值
1290. 二进制链表转整数 简单 方向恰好一致，边走边累积即可，无需任何反转结构
344. 反转字符串 简单 数组支持随机访问，对撞双指针原地交换即可，不必借助栈
20. 有效的括号 简单 栈用于维护待匹配状态而非反转顺序，是栈的另一类典型用法
232. 用栈实现队列 简单 两个栈倒腾一次即把后进先出转成先进先出，把反转性质用了两遍
150. 逆波兰表达式求值 中等 栈保存待运算的操作数，遇运算符弹两个，注意减除的操作数顺序