题目
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]
0 <= 链表长度 <= 10000
示例1
输入： {1,2,3}
返回值： [3,2,1]
示例2
输入：{67,0,24,58}
返回值：[58,24,0,67]
解答 1
知识点
递归：调用自身，分解问题，将大型问题转化为与原问题等价的小规模问题。
思路
链表无法逆序访问，可通过递归从底层往上回溯的方式遍历链表。
终止条件：递归进入链表尾（节点为空）
返回值：每次返回子问题之后的全部输出
本级任务： 每级子任务递归地进入下一级，等下一级的子问题输出数组返回时，将自己的节点值添加在数组末尾。
步骤
step 1：从表头开始往后递归进入每一个节点。
step 2：遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组。
step 3：直到递归返回表头。
java代码
import java.util.ArrayList;
public class Solution {
//递归函数
public void recursion(ListNode head, ArrayList<Integer> res){
if(head != null){
//先往链表深处遍历
recursion(head.next, res);
//再填充到数组就是逆序
res.add(head.val);
}
}
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<Integer>();
//递归函数解决
recursion(listNode, res);
return res;
}
}
复杂度分析：
时间复杂度：O(n)，其中n为链表长度，递归遍历一次链表
空间复杂度：O(n)，递归栈的最大空间为链表长度
解答 2
知识点
栈：对表尾进行插入删除的线性表（栈顶）。入栈或者出栈（退栈）针对的是栈顶
思路
用栈实现递归，因为栈是先进后出的，符合逆序的特点，
如同：往圆通里放乒乓球，先放入的的靠近圆筒底部，后放入的靠近圆筒入口。取出这些球则需要先取出后放入圆筒的球（后进先出）。
具体做法：
step 1：我们可以顺序遍历链表，将链表的值push到栈中。
step 2：然后再依次弹出栈中的元素，加入到数组中，即可实现链表逆序。
java代码
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<Integer>();
Stack<Integer> s = new Stack<Integer>();
//正序输出链表到栈中
while(listNode != null){
s.push(listNode.val);
listNode = listNode.next;
}
//输出栈中元素到数组中
while(!s.isEmpty()){
res.add(s.pop());
}
return res;
}
}
复杂度分析：
时间复杂度：O(n)，遍历链表是一个O(n)，弹空一个栈需要O(n)
空间复杂度：O(n)，栈空间最大长度是链表的长度n
原文链接：https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=23278&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
