import java.util.ArrayList;

import java.util.Stack;

/**

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

 */

class Test13 {

    public static void main(String[] args) {

        //创建单链表

        ListNode node1 = new ListNode(1);

        ListNode node2 = new ListNode(2);

        ListNode node3 = new ListNode(3);

        node1.next = node2;

        node2.next = node3;

        //采用递归的方式实现

        PrintListTailtoHead p = new PrintListTailtoHead();

        ArrayList<Integer> list = p.printListFromTailToHead(node1);

        System.out.println(list.toString());

        System.out.println("-------------");

        //借助堆栈的“后进先出”实现（容易理解）

        PrintListTailtoHead2 p2 = new PrintListTailtoHead2();

        ArrayList<Integer> list2 = p2.printListFromTailToHead2(node1);

        System.out.println(list2.toString());

    }

}

//节点

class ListNode {

    int value;

    ListNode next = null;

    ListNode() {}

    ListNode(int value) {

        this.value = value;

    }

}

//方法1：采用递归的方式实现

class PrintListTailtoHead {

    public ArrayList<Integer> printListFromTailToHead(ListNode headNode) {

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

        //递归

        if (headNode != null) {

            if (headNode.next != null) {

                list =printListFromTailToHead(headNode.next);

            }

            list.add(headNode.value);

        }

        return list;

    }

}

//方法2：借助堆栈的“后进先出”实现

class PrintListTailtoHead2{

    public ArrayList<Integer> printListFromTailToHead2(ListNode headNode) {

        //存入栈中

        Stack<Integer> stack=new Stack<Integer>();

        while (headNode!=null){

            stack.push(headNode.value);

            headNode=headNode.next; //重要，不要忘记

        }

        //从栈中取出存入集合中

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

        while (!stack.empty()) {

            arrayList.add(stack.pop());

        }

        //返回结果

        return arrayList;

    }

}