剑指offer——从尾到头打印链表

输入一个链表，从尾到头打印链表每个节点的值。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
    }
}

　　

可以利用栈的先入后出的特点，顺序遍历链表，将数据压入栈中，最后在从栈中弹出到结果ArrayList中即可

ArrayList的初始化

ArrayList<Integer> arrayList = new ArrayList<Integer>();

　　

其次，集合的大小用size()，数组的大小用length()

ArrayList的t添加：add(E object)

获取：get(int location)

ArrayList的遍历方式

public class ArrayListDemo {  
    public static void main(String[] args) {  
        List<String> al = new ArrayList<String>();  
        al.add("wangw1");  
        al.add("wangw3");  
        al.add("wangw4");  
        al.add("wangw5");  
          
        //遍历方式1  
        Iterator<String> it1 = al.iterator();  
        while(it1.hasNext()){  
            System.out.println(it1.next());  
        }  
          
        //遍历方式2  
        for(Iterator it2 = al.iterator();it2.hasNext();){  
            System.out.println(it2.next());  
        }  
          
        //遍历方式3  
        for(String temp:al){  
            System.out.println(temp);  
        }  
          
        //遍历方式4  
        for(int i = 0;i<al.size();i++){  
            System.out.println(al.get(i));  
        }  
    }  
}  

　　

自己的解法：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null || listNode.next == null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> array = new ArrayList<Integer>();
        ListNode list = listNode;
        while(list.next != null){
            array.add(list.val);
            list = list.next;
        }
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        arrayList.add(list.val);
        for(int i = array.size() - 1; i >= 0; --i ){
            arrayList.add(array.get(i));
        }
        return arrayList;
    }
}

　　

利用栈：

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

　　

别人的递归调用：

注意返回结果arrayList是定义在外面的，而且，里面遍历链表是用的if，不是循环

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