剑指offer【03】 从尾到头打印链表(4种实现方法)

题目：从尾到头打印链表

考点：链表

题目描述：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

 

法一：ArrayList头插法

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    //ArrayList头插法实现栈功能
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        while(listNode != null){
           //0 是插入的为值  val 就是吧每次的值取出来插入到0的位置。其他之前的插入的向后顺序移动。
           list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}

法二：使用Collections的reverse方法，将list反转

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.Collections;
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        while(listNode != null){
           list.add(listNode.val);
           listNode = listNode.next;
        }
        //使用Collections的reverse方法，直接将list反转
        Collections.reverse(list);
        return list;
    }
}

法三：递归法

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

递归的点在printListFromTailToHaed(listNode.next)这个节点，那么在最后一次递归方法返回以后，每一层的递归方法都会做一个arrayList.add(lizxstNode.val)这个操作，从最后一次到第一次，逆向的调用了后面的方法。因为之前的递归点已经返回了。

法四：用栈实现

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.Collections;
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    Stack<ListNode> stack = new Stack<ListNode>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        while(listNode != null){
            stack.push(listNode);
            listNode = listNode.next;
        }
        //利用栈后进先出的特点实现翻转
        while(!stack.isEmpty()){
            list.add(stack.pop().val);
        }
        return list;
    }
}