3. 从尾到头打印链表

3.1 题目

输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

3.2 解题思路

• 使用栈。
• 将链表从头到尾压入栈中，出栈的过程就对应着从尾到头。

3.3 实现代码

有两种解法，任选一种。

public class Test { 
    // 结点对象
    public static class ListNode { 
        int val; // 结点的值 
        ListNode nxt; // 下一个结点
    }
    
    /** 
     * 输入个链表的头结点，从尾到头反过来打印出每个结点的值 
     * 使用栈的方式进行，栈为先入后出的方式
     * @param root 链表头结点 
     */
    public static void printListInverselyUsingIteration(ListNode root) {
        Stack<ListNode> stack = new Stack<>(); //创建栈，指定泛型为ListNode
        while(root != null) { //如果节点不为空
            stack.push(root); //把节点压入栈
            root = root.next; //指向下一个节点
        } 
        ListNode tmp; //创建一个临时ListNode对象
        while(!stack.isEmpty()) { 
            tmp = stack.pop(); //出栈方法的返回值就是一个节点
            System.out.print(tmp.val + " "); //一个个把节点的值给输出
        }
    }
}

 /** 
     * 输入个链表的头结点，从尾到头反过来打印出每个结点的值 
     * 使用递归的方式进行 
     * @param root 链表头结点 
     */
    public static void printListInverselyUsingRecursion(ListNode root){ //递归方式时间超出，在牛客网上未通过。用栈
        if(root != null) { 
            printListInverselyUsingRecursion(root.next); //递归
            System.out.print(root.val + " ");
        }
    }

递归方式时间超出，在牛客网上未通过。得用栈。