逆序打印单链表

题目描述：

逆序打印单链表，要求不能改变链表结构。

思路分析：

由于单链表只能顺序遍历(从头到尾遍历)而不能逆向遍历，所以，要逆序打印单链表，则必需要用到先进后出的数据结构，先进后出的数据结构，我们很容易想到栈。

而运用了栈结构的实现主要有两种：

1. 递归：递归内部包括了一个方法调用栈。

2. Stack：Java中栈数据结构的默认实现。

代码实现：

方法1：递归实现

// 使用递归实现链表逆序打印
public void reversePrint(LinkedNode node) {
    if (node == null) {
        return;
    }
    reversePrint(node.next);
    System.out.println(node.element);
}

方法2：循环实现

// 使用栈(Stack)逆序打印单链表
public void reversePrint(LinkedNode header) {
    Stack<LinkedNode> stack = new Stack<>();
    LinkedNode currentNode = header;
    while (currentNode != null) {
        stack.push(currentNode);
        currentNode = currentNode.next;
    }
    while (stack.size() > 0) {
        LinkedNode node = stack.pop();
        System.out.println(node);
    }
}

总结：

由于单链表无法逆序遍历，而且题目要求不得改变链表结构，因此只能使用先进后出的数据结构(栈)。

而递归方法的调用顺序就正好是一个先进后出的结构，因此可以使用递归实现。当然，也可以借助外部存储空间实现，比如栈，集合等，当然，栈比集合是更合适的选择。