输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

1. 利用栈

由于是先进后出，可以很显然想到栈。

    public static ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        Deque<Integer> dq = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();     //使用Deque模拟栈
        if (listNode == null) {
            return list;               //返回空
        }
        while (listNode != null) {
            dq.addFirst(listNode.val);
            listNode = listNode.next;
        }
        while (!dq.isEmpty()) {
            list.add(dq.pollFirst());
        }
        return list;
    }

也可以更简单的实现

 public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode tmp = listNode;
        while(tmp!=null){
            list.add(0,tmp.val);       //先进后出
            tmp = tmp.next;
        }
        return list;
    }

复杂度都是O(n)，但第二个更好点。

2. 递归

递归到最后一个节点，然后回溯。

  ArrayList<Integer> list = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        if(listNode!=null){
            printListFromTailToHead3(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }