从头到尾打印链表

题目描述：

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList

 

思路：

方法一：

可以采用栈的先进后出实现

代码：

import java.util.ArrayList;
import java.util.Stack;

public class test031 {
    public static class ListNode {
        int val;       //结点的值
        ListNode next = null;    //下一个结点
    }


    public static class Solution {
        /*
           使用栈的方式
        */
        public ArrayList<Integer> test(ListNode listNode) {
            Stack<Integer> stack = new Stack<>();
            while (listNode != null) {
                stack.push(listNode.val);       //进栈
                listNode = listNode.next;
            }

            ArrayList<Integer> list = new ArrayList<>();
            while (!stack.isEmpty()) {
                list.add(stack.pop());
            }

            return list;
        }
    }


    public static void main(String[] args) {
        ListNode node = new ListNode();
        node.val = 1;
        node.next = new ListNode();
        node.next.val = 2;
        node.next.next = new ListNode();
        node.next.next.val = 3;
        node.next.next.next = new ListNode();
        node.next.next.next.val = 4;

        Solution solution = new Solution();


        ArrayList<Integer> list = solution.test(node);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }

    }
}

方法二：

使用递归实现

代码：

import java.util.ArrayList;

public class test032 {
    public static class ListNode {
        int val;       //结点的值
        ListNode next = null;    //下一个结点
    }

    public static class Solution {
        ArrayList<Integer> list=new ArrayList<Integer>();
        public ArrayList<Integer> test(ListNode listNode) {
            if(listNode!=null){
                this.test(listNode.next);
                list.add(listNode.val);
            }
            return list;
        }
    }

    public static void main(String[] args) {
        ListNode node = new ListNode();
        node.val = 1;
        node.next = new ListNode();
        node.next.val = 2;
        node.next.next = new ListNode();
        node.next.next.val = 3;
        node.next.next.next = new ListNode();
        node.next.next.next.val = 4;


        Solution solution = new Solution();
        ArrayList<Integer> list = solution.test(node);
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i)+" ");
        }
    }
}