从头到尾打印链表

1.题目
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
如，输入：{67,0,24,58}；输出：[58,24,0,67]
2.思路：
方法一：这种反向输出很容易想到了栈

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

但是有人用ArrayList的特性，ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入value值，所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置，最后输出 listNode 即可得到逆序链表,这样代码更为简便

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;
    }
}

方法二：利用递归的思想，递归到最后慢慢一层层输出也是一种逆序，因为其借用了计算机系统本身用栈存储的思想

import java.util.ArrayList;
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;
    }
}