面试题6：从尾到头打印链表

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
/**
 * 面试题6：从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来打印出每个节点的值
 */
public class No6 {
    public static void main(String[] args) {
        //测试用例
        //1、输入的链表有多个（1个）节点
        //2、特殊输入测试
        ListNode test = new ListNode();
        test.add(4);
        test.add(5);
        test.add(6);
        test.print();
        System.out.println(methord2(test));
    }
    //栈实现。鲁棒性优于递归调用
    public static ArrayList<Integer> methord1(ListNode listNode){
        ArrayList<Integer> array = new ArrayList<>();
        Stack<ListNode> stack = new Stack<>();
        while(listNode != null){
            stack.push(listNode);
            listNode = listNode.next;
        }
        while(!stack.empty()){
            array.add(stack.pop().val);
        }
        return array;
    }
    //递归实现.注意，如果链表很长时，会导致函数调用层级很深，有可能导致函数调用栈溢出。
    public static ArrayList<Integer> methord2(ListNode listNode){
        ArrayList<Integer> array = new ArrayList<>();
        if(listNode!=null){
            if(listNode.next!=null){
                array = methord2(listNode.next);
            }
            array.add(listNode.val);
        }
        return array;
    }
    static class ListNode {
    int val;    //数值 data
    ListNode next;    // 结点 node
    ListNode(int x) {    //可以定义一个有参构造方法，也可以定义一个无参构造方法
        val = x;
    }
    public ListNode() {
    }
    // 添加新的结点
    public void add(int newVal) {
        ListNode newNode = new ListNode(newVal);
        if (this.next == null)
            this.next = newNode;
        else
            this.next.add(newVal);
    }
    // 打印链表
    public void print() {
        System.out.print(this.val);
        if (this.next != null) {
            System.out.print("-->");
            this.next.print();
        }
    }
}
}