从尾到头打印链表【Java版】

1）递归方法（系统栈）

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();　　//一定要在函数之前定义
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            printListFromTailToHead(listNode.next);    //没有用到printListFromTailToHead的返回值
            res.add(listNode.val);    //这个在递归后面，则可以做到倒序；如果在递归前就是正序
        }
        return res;
    }
}

2）自己写栈

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

3）头插法

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer>mylist=new ArrayList<>();//含有<>和（）；别忘了new
        while(listNode!=null){//直接用null对应listNode就行
            mylist.add(0,listNode.val);//list.add(0,value)在list的头部插入值
            listNode=listNode.next;//Java这样就不用到->指针了，只会用到STL里面定义过的操作
        }
        return mylist;
    }
}

这三种方法复杂度都是：空间O(N) 时间O(N)