法一 新建数组，倒序存储

一遍历得长度，据此新建等长数组，二遍历倒序存储

时间复杂度：O（N），但是是两次 空间复杂度：O（N）

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //创建一等长数组，逆序存储
        ListNode p = listNode;
        int n = 0;
        while(p != null){
            n++;
            p = p.next;
        }
        
        int[] res = new int[n];
        int i = n-1;
        p = listNode;
        while(p != null && i >=0){
            res[i] = p.val;
            p = p.next;
            i--;
        }
      	//注意这种写法
        return new ArrayList<Integer>(){
            {
                for(int t: res){
                    add(t);
                }
            }
        };

可见，这种很差劲

法二 使用辅助栈

一次遍历，元素入栈；再次遍历，出栈到结果ArrayList中

时间复杂度：O（N），两次

空间复杂度：O（N）

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //使用辅助栈
        Deque<Integer> stack = new LinkedList<Integer>();
        ListNode p = listNode;
        
        while(p != null){
            stack.push(p.val);
            p = p.next;
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(!stack.isEmpty()){
            res.add(stack.pop());
        }       
        return res;
    }

可见，效率依然很差

法三 直接遍历，后反转ArrayList

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode p = listNode;
        ArrayList<Integer> res = new ArrayList<Integer>();
        
        while(p != null){
            res.add(p.val);
            p = p.next;
        }
        Collections.reverse(res);
        return res;
    }

依然很差

法四 反转链表，然后遍历添加

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode p = listNode;
        ArrayList<Integer> res = new ArrayList<Integer>();
        p = reverse(p);
        while(p != null){
            res.add(p.val);
            p = p.next;
        }       
        return res;
    }
    
    private ListNode reverse(ListNode head){
        ListNode pre = null,
            cur = head,
            temp = cur;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

为什么还是这么差