题目06：从尾到头打印链表

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

思路

一. 栈

从头遍历链表，先访问的后输出，后访问的先输出，“后进先出”，利用栈来实现

二. 递归

递归本质上就是一个栈的结构，可以利用递归来实现。但是当链表比较长的时候，递归会导致函数调用的层级很深，有可能会导致函数调用栈的溢出

代码实现

import java.util.Stack;

public class _06 {
    private static class ListNode {
        private int val;
        private ListNode next;

        public ListNode(int value) {
            this.val = value;
        }
    }
 
    public static void printListInversely1(ListNode root) {//用栈
        Stack<ListNode> stack = new Stack<>();
        while (root != null) {
            stack.push(root);
            root = root.next;
        }
        ListNode tmp;
        while (!stack.isEmpty()) {
            tmp = stack.pop();
            System.out.print(tmp.val + " ");
        }
    }

    public static void printListInversely2(ListNode root) {//递归
        if (root != null) {
            printListInversely2(root.next);
            System.out.print(root.val + " ");
        }
    }
 
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next =n2;
        n2.next =n3;
        n3.next =n4;
        n4.next =n5;

        printListInversely1(n1);
        System.out.println();
        printListInversely2(n1);
    }
}

输出：

5 4 3 2 1 
5 4 3 2 1