从尾到头打印链表

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

解决方法：

1. 使用 栈 (后进先出) ，遍历链表(从头到尾),输出是从尾到头
2. 递归 (递归的本质也是一个栈结构)
3. 头插法 (链表头插法为逆序)

代码实现：

/**
 * 题目类型：链表
 *
 * 题目要求：输入一个链表的头节点，从尾到头反过来打印出每个节点的值
 *
 *思路：1. 遍历链表(从头到尾),输出是从尾到头，因此使用 栈 (后进先出)
 *
 * 2. 递归 (递归的本质也是一个栈结构)
 *
 * 3. 链表头插法(逆序)
 */
public class PrintLinkedList {

    public static class ListNode {

        private int value; // 节点的值

        private ListNode next;  // 下一个节点
    }

    /**
     * 方式 1 ：使用栈的方式
     *
     * @param root 头节点
     */
    public static void printListFromTailToHead(ListNode root) {
        Stack<ListNode> stack = new Stack<>();
        while (root != null) {
            stack.push(root);
            root = root.next;
        }

        ListNode temp;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            System.out.print(temp.value + " ");
        }
    }

    /**
     * 方式 2 ：递归
     *
     * @param root
     */
    public static void printListByRecursion(ListNode root) {
        if (root != null) {
            printListByRecursion(root.next);
            System.out.print(root.value + " ");
        }
    }

    /**
     * 方式 3 ：头插法 (链表头插法为逆序) 尾插法为顺序
     *
     * 头节点和第一个节点的区别：
     *      1. 头节点是在头插法中使用的一个额外节点，该节点不存储值
     *      2. 第一个节点就是链表第一个真正存储值的节点
     *
     *时间复杂度：每个节点插入的时间为 O(1),设单链表长为 n，则 T(n) = O(n )
     *
     * @param root 原链表的头节点
     */
    public static void printListByHeadInsertion(ListNode root) {
        // 头插法构建逆序链表(新的链表的头节点)
        ListNode head = new ListNode();
        while (root != null) {
            ListNode listNode = root.next; // listNode指向原链表的第二个节点
            root.next = head.next; // 断开原链表头节点与其下一节点的连接
            head.next = root; // 新链表的头结点的下一节点指向原链表的头节点
            root = listNode;// 相当于 root = root.next
        }

        // 构建ArrayList
        ArrayList<Integer> ret = new ArrayList<>();
        head = head.next;
        while (head != null) {
            ret.add(head.value);
            head = head.next;
        }

        for (int nodeValue : ret) {
            System.out.print(nodeValue + " ");
        }
    }


    public static void main(String[] args) {
        ListNode root = new ListNode();
        root.value = 1;

        root.next = new ListNode();
        root.next.value = 2;

        root.next.next = new ListNode();
        root.next.next.value = 3;

        root.next.next.next = new ListNode();
        root.next.next.next.value = 4;

        root.next.next.next.next = new ListNode();
        root.next.next.next.next.value = 5;

        System.out.print("栈的方式：");
        printListFromTailToHead(root);
        System.out.println();
        System.out.println();
        System.out.print("递归(本质也是栈)的方式：");
        printListByRecursion(root);
        System.out.println();
        System.out.println();
        System.out.print("头插法的方式：");
        printListByHeadInsertion(root);
    }
}