1. 递归

1.1 分析

递归的关键，先向下递归再执行本次操作，这样才会形成反序操作序列。递归结束时没有操作，结束的上一步中的操作是反序操作的第一步，在本题中就是list.add(tail.val)。

1.2 代码

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

1.3 复杂度

空间：O(n)
时间：O(n)

2. 非递归

2.1 分析

利用ArrayList中add(index,value)的方法，实施头插法。

2.2 代码

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

2.3 复杂度

空间：O(1)
时间：O(n)

3. 栈

3.1 分析

借助栈，先入后出

3.2 代码

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

3.3 复杂度

空间 ：O(n)
时间 : O(n)