題目：輸入一個鏈表的頭節(jié)點，從尾到頭反過來打印出每個節(jié)點的值

解決方法：

1. 使用 棧 (后進先出) ，遍歷鏈表(從頭到尾),輸出是從尾到頭
2. 遞歸 (遞歸的本質也是一個棧結構)
3. 頭插法 (鏈表頭插法為逆序)

代碼實現(xiàn)：

/**
 * 題目類型：鏈表
 *
 * 題目要求：輸入一個鏈表的頭節(jié)點，從尾到頭反過來打印出每個節(jié)點的值
 *
 *思路：1. 遍歷鏈表(從頭到尾),輸出是從尾到頭，因此使用 棧 (后進先出)
 *
 * 2. 遞歸 (遞歸的本質也是一個棧結構)
 *
 * 3. 鏈表頭插法(逆序)
 */
public class PrintLinkedList {

    public static class ListNode {

        private int value; // 節(jié)點的值

        private ListNode next;  // 下一個節(jié)點
    }

    /**
     * 方式 1 ：使用棧的方式
     *
     * @param root 頭節(jié)點
     */
    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 ：頭插法 (鏈表頭插法為逆序) 尾插法為順序
     *
     * 頭節(jié)點和第一個節(jié)點的區(qū)別：
     *      1. 頭節(jié)點是在頭插法中使用的一個額外節(jié)點，該節(jié)點不存儲值
     *      2. 第一個節(jié)點就是鏈表第一個真正存儲值的節(jié)點
     *
     *時間復雜度：每個節(jié)點插入的時間為 O(1),設單鏈表長為 n，則 T(n) = O(n )
     *
     * @param root 原鏈表的頭節(jié)點
     */
    public static void printListByHeadInsertion(ListNode root) {
        // 頭插法構建逆序鏈表(新的鏈表的頭節(jié)點)
        ListNode head = new ListNode();
        while (root != null) {
            ListNode listNode = root.next; // listNode指向原鏈表的第二個節(jié)點
            root.next = head.next; // 斷開原鏈表頭節(jié)點與其下一節(jié)點的連接
            head.next = root; // 新鏈表的頭結點的下一節(jié)點指向原鏈表的頭節(jié)點
            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);
    }
}