耐心和持久胜过激烈和狂热。

题目来源

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

题目分析

将一个链表反向存到数组里，可以使用递归（本质就是栈）或数组反转的方式去实现。

解题思路

递归

很简单，递归到最后一个节点时回溯，往数组（Go 语言使用切片）里面添加元素

反转数组（切片）

遍历节点，然后往切片里添加元素，最后反转切片。

代码实现

递归

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

执行结果

复杂度分析

时间复杂度：O(N)，递归 N 次，遍历链表空间复杂度：O(N)，递归需要 O(N) 的栈空间

反转切片

func reversePrint(head *ListNode) []int {  var res []int  for head != nil {    res = append(res, head.Val)        head = head.Next  }  // 反转切片  for i, j := 0, len(res) - 1; i < j; i++ {    res[j], res[i] = res[i], res[j]        j--  }  return res}

执行结果

复杂度分析

时间复杂度：O(N)，一轮遍历链表，一轮遍历切片，使用 O(N) 的时间空间复杂度：O(N)，切片需要 O(N) 的空间

总结

根据执行结果可以看出，递归比非递归慢，原因是每次分配函数内存以及栈都需要时间。

以上是本人的解法，如果对你有帮助，欢迎点赞收藏加关注，如果有错误的地方，欢迎指正！