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

分析

既然要反向打印值，那么我们可以使用 栈 这种 后进先出 数据结构，每遍历一个节点后就将该节点入栈，等到节点遍历完后，就将栈中的元素出栈即可。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class PrintList {
    // 首先定义链表的结构体
    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
	}
    // 非递归实现
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next; //后移
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop()); //出栈的时候需要放在 list 中
        }
        return list;
    }

    // 递归实现
    static ArrayList<Integer> list_Recursively = new ArrayList<>();
    public static ArrayList<Integer> printListFromTailToHead_Recursively(ListNode listNode) {
        if (listNode != null) {
            printListFromTailToHead_Recursively(listNode.next);
            list_Recursively.add(listNode.val);
        }
        return list_Recursively;
    }
}

详解

对于非递归的方式，我们使用的是栈，第 16~18 行，只要该节点不为 null，就将其入栈，紧接着后移，直到最后一个节点为止。第 20~21 行，只要栈不为空，就出栈，并将节点添加到 list 中，最后将 list 返回。对于递归的方式，道理是一样的。