《剑指offer》 第6题 从尾到头打印链表

解法有很多，作为初学者，看了很多大佬的解法，很多大佬都用了头插法，头插法自然可以，也直观，问题在于题目的考点不在于这里，如果是机试可能没问题，如果是面试的话，可能还是得揣摩面试官想问的点是什么。另外，ArrayList是基于动态数组的实现，既然是数组，对数组头插的时间复杂度较高，一定要头插的话，应该还是LinkedList比较好。

思路1：一种经典的思想是将链表的元素入栈，利用栈的先进后出的特点，来进行逆序，这么经典的栈的使用，很符合这个题目要考的知识点。利用空间换时间。而且也不存在递归调用的栈溢出的情况。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        //也可以求链表长度，然后创建等长度的Stack，和ArrayList。
        //毕竟ArrayList和stact是可以动态扩容的，更严谨的写法应该要加入求长度的过程。
         while(listNode != null){
             stack.push(listNode.val);
             listNode = listNode.next;
         }
        while(!stack.isEmpty()){
            array.add(stack.pop());
        }  
        return array;
    }
}

思路2：
头插法

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();        
        while (listNode != null) {
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}