LeetCode 剑指 Offer 06. 从尾到头打印链表
题目描述
题意分析
返回一个数组，按原链表从尾到头的顺序保存所有节点值。要反过来的是输出顺序，不需要把链表本身反转，也不需要修改任何节点的
next连接。单链表只能从头沿
next前进，不能直接从尾节点走回前一个节点。因此先顺序保存沿途的值，再从保存结果的末尾开始读取。
解法：收集节点值后逆序输出
核心思路
[!blue]
从头遍历时，第一个读到的是头节点，最后一个读到的是尾节点。要让最后读到的值最先输出，可以借助栈的后进先出顺序：依次压入所有节点值，再依次弹出，就恰好得到从尾到头的排列。
Java 直接用
Deque作为栈，遍历结束时栈顶保存尾节点值。Go 的切片先按链表顺序追加值，再用下标反向访问：答案位置i对应保存数组的位置n-1-i。两种方式都将原来第j个值放到逆序后的第n-1-j个位置，每个值恰好输出一次。第一遍结束后才知道节点数量，此时创建相同长度的结果数组。遍历只移动函数内部的
head引用，没有给任何节点的连接赋值，所以原链表结构保持不变。
解题步骤
- 从
head出发，沿next逐个访问节点，将值压入栈或追加到切片。- 遍历到空指针后，按已保存的值的数量分配结果数组。
- Java 持续弹栈并从结果开头写入；Go 从保存切片的末尾向前读取，写入结果。
- 返回数组。空链表不保存任何值，结果长度自然为零。
代码实现
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(n)$，用于保存全部节点值；返回数组本身也占 $O(n)$。
关键点总结
[!green]
- 保存顺序与链表一致，读取顺序与保存顺序相反，从而得到逆序输出。
- Java 弹栈会缩短容器，所以先固定结果长度，再以栈是否为空控制输出；Go 按下标读取，切片长度保持不变。
- 移动遍历指针不会修改节点连接，可以完整保留原链表。
易错点总结
[!yellow]
- 直接按链表遍历顺序追加结果，只能得到正序。
- 边弹栈边使用不断变小的栈长度作为固定循环上限，会少处理元素。
- 未经保存就改动 next，可能丢失后续节点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 445. 两数相加 II | 中等 | 栈可补足单链表从尾部访问的能力，原题逆向处理数字加法，本题只逆序输出。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！