从尾到头打印链表-Java

package algorithm;

import java.util.Stack;

public class ReverseLinkedList {

  /**
   * 借助栈，这个数据结构
   * 缺点是需要额外空间
   *
   * @param node 链表头结点
   */
  public static void printReverseLinkedList(Node node) {
    if (node == null) return;
    Stack<Integer> stack = new Stack<>();
    while (node != null) {
      stack.push(node.val);
      node = node.nextNode;
    }

    while (!stack.isEmpty()) {
      System.out.println(stack.pop());
    }
  }

  /**
   * 使用递归思想，要反过来输出链表，我们每访问一个节点时，先输出它后面的节点
   * 再输出自身节点；这样输出结果就反过来了
   *
   * @param node 头结点
   */
  public static void printReverseRecursive(Node node) {
    if (node == null) return;
    printReverseLinkedList(node.nextNode);
    System.out.println(node.val);
  }

  public static void main(String[] args) {
    Node node1 = new Node(10);
    Node node2 = new Node(11);
    Node node3 = new Node(12);
    Node node4 = new Node(13);
    Node node5 = new Node(14);
    Node node6 = new Node(15);
    node1.nextNode = node2;
    node2.nextNode = node3;
    node3.nextNode = node4;
    node4.nextNode = node5;
    node5.nextNode = node6;
    node6.nextNode = null;

//    printReverseLinkedList(node1);
    printReverseRecursive(node1);
  }
}

class Node {
  public int val;

  public Node nextNode;

  public Node(int val) {
    this.val = val;
  }
}