您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode如何从尾到头打印链表
## 问题描述
题目链接：[剑指 Offer 06. 从尾到头打印链表](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)
**题目要求**：
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
**示例**：
```python
输入：head = [1,3,2]
输出：[2,3,1]
链表是一种线性数据结构，通过指针将零散的内存块串联起来。每个节点包含： - 数据域（存储值） - 指针域（存储下一个节点的地址）
本题中的链表是单向链表，只能从头节点开始顺序访问。
由于链表是单向的，无法直接逆向访问节点。需要找到一种方法，在不修改链表结构的前提下实现逆向输出。
利用栈的后进先出（LIFO）特性实现逆序： 1. 遍历链表，将节点值依次压入栈 2. 弹出栈中元素存入结果数组
def reversePrint(head):
stack = []
while head:
stack.append(head.val)
head = head.next
return stack[::-1] # 反向切片等效于出栈
# 显式使用栈操作
def reversePrint(head):
stack = []
res = []
while head:
stack.append(head.val)
head = head.next
while stack:
res.append(stack.pop())
return res
利用递归的回溯阶段实现逆序输出： 1. 递归到链表末尾 2. 回溯时收集节点值
def reversePrint(head):
return recur(head, [])
def recur(node, res):
if not node:
return res
res = recur(node.next, res)
res.append(node.val)
return res
链表较长时可能导致栈溢出，实际工程中建议使用栈辅助法。
def reversePrint(head):
length = 0
curr = head
while curr:
length += 1
curr = curr.next
res = [0] * length
curr = head
for i in range(length-1, -1, -1):
res[i] = curr.val
curr = curr.next
return res
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 栈辅助法 | O(n) | O(n) | 通用解法 |
| 递归法 | O(n) | O(n) | 链表较短时 |
| 两次遍历法 | O(n) | O(1) | 空间限制严格时 |
实际编码时需考虑：
1. 空链表输入：head = None
2. 单节点链表：head = [1]
3. 大规模链表测试（特别是递归法）
可采用链表反转法： 1. 先反转链表 2. 顺序遍历存储值 3. 恢复链表原状（如有需要）
def reversePrint(head):
if not head:
return []
# 反转链表
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
# 存储结果
res = []
while prev:
res.append(prev.val)
prev = prev.next
return res
从尾到头打印链表是考察逆向思维的经典题目，主要解决方案包括： 1. 栈辅助法：最直观的解法，推荐掌握 2. 递归法：简洁但需注意栈深度 3. 两次遍历法：空间最优解
建议在面试中： 1. 首先说明所有可能的解法 2. 分析各方法优劣 3. 选择最合适的方法实现
”`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。