一、题目
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]
二、题解
看到这题很多人第一反应是从头到尾输出会比较简单，于是我们很自然想到把链表中的节点指针反过来，改变链表结构就可以从头到尾输出了。但该方法会改变原来链表的结构。
是否允许在打印链表的时候修改链表结构？在面试的时候我们需要问清楚面试官的需求。
一般来说，打印是一个只读的操作，而不希望打印时修改内容，现假设面试官要求我们不能修改链表的结构。
2.1 利用Stack栈实现
解决这个问题肯定要遍历链表。遍历的顺序是从头到尾，可输出的顺序确实从尾到头。也就是说第一个遍历的最后一个输出，最后一个遍历的第一个输出。
这就是典型的”后进先出“，于是我们想到栈这种数据结构。
每经过一个节点的时候，把这个节点的值放入栈中，等到遍历完链之后再从栈顶开始逐个输出节点的值。
代码如下：
import java.util.*;
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
//ListNode node = listNode;
while(listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.empty()){
list.add(stack.pop());
}
return list;
}
}2.2 利用ArrayList实现
ArrayList本身也可以实现类似栈的功能，list.add(0, xxx)即可插入头部
这样的话代码就非常简洁，只需遍历链表，每个节点的值从头插入数组即可
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<Integer>();
while(listNode != null){
res.add(0,listNode.val);
listNode = listNode.next;
}
return res;
}
}