从尾到头打印链表 - JZ17
题目描述
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。
返回的结果用数组存储。
数据范围： 0 ≤ 链表长度 ≤ 1000
样例：
- 输入：[2, 3, 5]
- 返回：[5, 3, 2]
解题思路
这道题有多种解法：
- 栈辅助法： 利用栈的后进先出特性
- 递归法： 利用递归的天然栈性质
- 反转后遍历： 先反转链表再正向遍历
- 两次遍历： 先计算长度，再逆向填充数组
项目结构
.
├── go.mod # Go 模块定义
├── types.go # 链表类型定义和工具函数
├── solution.go # 算法实现（你需要完成这个文件）
├── answer.go # 参考答案（练习后查看）
├── main.go # 主函数和测试用例
├── solution_test.go # 单元测试
└── README.md # 说明文档
使用方法
1. 实现算法
在 solution.go 文件中实现以下函数：
printListFromTailToHead(head *ListNode) []int- 主要实现
可选实现多种解法：
printListFromTailToHeadByStack(head *ListNode) []int- 栈辅助法printListFromTailToHeadByRecursion(head *ListNode) []int- 递归法printListFromTailToHeadByReverse(head *ListNode) []int- 反转后遍历printListFromTailToHeadByTwoPass(head *ListNode) []int- 两次遍历
2. 运行测试
# 运行主程序，查看测试结果
go run .
# 运行单元测试
go test -v
# 运行基准测试
go test -bench=.
3. 检查代码格式
# 格式化代码
go fmt ./...
# 代码检查
go vet ./...
时间和空间复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 栈辅助法 | O(n) | O(n) | 需要额外栈空间 |
| 递归法 | O(n) | O(n) | 递归调用栈 |
| 反转后遍历 | O(n) | O(1) | 会修改原链表 |
| 两次遍历 | O(n) | O(1) | 不修改原链表 |
知识点
- 链表的遍历
- 栈的应用
- 递归思想
- 空间与 时间的权衡