題目
輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值（用數組返回）。

示例 1：
輸入：head = [1,3,2]
輸出：[2,3,1]

限制：
0 <= 鏈表長度 <= 10000

解法一：遞歸（遞歸本來就是一種棧，所以算做一類）

func reversePrint(head *ListNode) []int {if head == nil {return []int{}}if head.Next == nil {return []int{head.Val}}return append(reversePrint(head.Next), head.Val) }

解法二：逆置鏈表

func reversePrint(head *ListNode) []int {if head == nil {return []int{}}// 逆置鏈表fistNode, mindNode := head, head.NextfistNode.Next = nilfor {if mindNode == nil {break}endNode := mindNode.NextmindNode.Next = fistNodefistNode = mindNodemindNode = endNode}vals := make([]int,0)for {if fistNode == nil {return vals}vals = append(vals, fistNode.Val)fistNode = fistNode.Next} }

解法三：頭部動態插入（模擬切片動態擴容）

func reversePrint(head *ListNode) []int {if head == nil {return []int{}}vals := make([]int, 4)endIndex := len(vals)for {endIndex--if head == nil {break}vals[endIndex] = head.Valif endIndex == 0 {vals, endIndex = dilatation(vals)}head = head.Next}return vals[endIndex+1:] }func dilatation(arr []int) ([]int, int) {lenArr := len(arr)restfulSize := lenArr + lenArr/2restful := make([]int, restfulSize)endIndex := len(restful)arrIndex := lenArr - 1for {if arrIndex < 0 {break}endIndex--restful[endIndex] = arr[arrIndex]arrIndex--}return restful, endIndex }

總結：可以看出頭部動態插入與逆置鏈表再執行速度相同的情況下占用的空間還是比遞歸少一些，雖然不是官方解法。

總結

以上是生活随笔為你收集整理的剑指 Offer 06. 从尾到头打印链表(递归、逆置链表、头部动态插入)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。