输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
解法
首先，我们假设val代表某一节点的数据值。
解法一：初看题目意思就是输出的时候链表尾部的元素放在前面，链表头部的元素放在后面。这不就是先进后出，后进先出么。什么数据结构符合这个要求？栈！
importjava.util.ArrayList;importjava.util.Stack;publicclassSolution{publicArrayList<Integer>printListFromTailToHead(ListNodelistNode){//使用栈这种数据结构Stack<Integer>stack=newStack<>();//将链表元素全部存放在栈里面while(listNode!=null){stack.add(listNode.val);listNode=listNode.next;}ArrayList<Integer>ret=newArrayList<>();//取出栈里面的元素while(!stack.isEmpty())ret.add(stack.pop());returnret;}}
以“先进后出”的规则将链表数据放置到栈中，然后用数组取出。。。
解法二：第二种方法也比较容易想到，通过链表的构造，如果将末尾的节点存储之后，剩余的链表处理方式还是不变，所以可以使用递归的形式进行处理。代码如下：
importjava.util.ArrayList;publicclassSolution{publicArrayList<Integer>printListFromTailToHead(ListNodelistNode){ArrayList<Integer>ret=newArrayList<>();if(listNode!=null){ret.addAll(printListFromTailToHead(listNode.next));ret.add(listNode.val);}returnret;}}
这里以数组方式直接存储，采用递归，使代码更简洁易懂。
但是，这道题不管怎么做都是O(n)的时间复杂度，用栈实现的解法一会多了O(n)的空间复杂度，用递归实现的解法二会存在栈溢出的可能，而下面介绍的是比较优的解法，把链表逆序再插入，或者插入再把数组逆序，都是简单又省事。而且，递归实现对于程序来说，实属不明智之举动。
解法三：如果你还知道链表的更多性质的话，肯定能想到用头插法为逆序的特点来解决。头插法：将链表的左边称为链表头部，右边称为链表尾部。头插法是将右边固定，每次新增的元素都在左边头部增加。
publicArrayList<Integer>printListFromTailToHead(ListNodelistNode){//头插法构建逆序链表ListNodehead=newListNode(-1);while(listNode!=null){ListNodememo=listNode.next;listNode.next=head.next;head.next=listNode;listNode=memo;}//构建ArrayListArrayList<Integer>ret=newArrayList<>();head=head.next;while(head!=null){ret.add(head.val);head=head.next;}returnret;}
这里面第一段代码：通过不断的相互替换，达到“逆置链表”的目的（就如同初学C时的“用第三个杯子交换两个数”的问题）。
问题探索
想一想：栈和队列最大的一个区别是什么？优先队列和堆是什么关系？
