从尾到头打印链表【Java版】
从尾到头打印链表
http://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035
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)
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》