# 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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
