《剑指offer》面试题6：从尾到头打印链表

题目：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。（链表是单链表）

思路：由于单链表的特性，只能从头节点开始遍历链表，而打印顺序是从尾到头，故选用“栈”这种数据结构实现“先进后出”。JavaSE中有已经实现好的栈，可以直接使用；同时递归函数本质上也是一个栈结构，在不考虑栈溢出的情况下，也可以使用递归函数实现。

代码如下：

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

public class Solution {
    private ArrayList<Integer> arrayList = new ArrayList<>();
    /**
     * 使用JavaSE中的栈类实现
     * @param node
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead(Node node) {
        if (node == null) {
            return null;
        }
        Stack<Integer> stack = new Stack();
        while (node != null) {
            stack.push(node.data);
            node = node.next;
        }
        while (!stack.isEmpty()) {
            arrayList.add(stack.pop());
        }
        return arrayList;
    }

    /**
     * 利用递归实现栈
     * @param node
     * @return
     */
    public ArrayList<Integer> printLinkFromTailToHeadByRecursion(Node node) {
        if (node == null) {
            return null;
        }
        printLinkFromTailToHeadByRecursion(node.next);
        arrayList.add(node.data);
        return arrayList;
    }
}

节点类Node的定义参考文章：https://www.jianshu.com/p/b2c8f4951578
在笔试面试中，应当优先使用JavaSE中已经实现好的Stack栈类解题，提高代码的鲁棒性。