Linked List

关于链表的基本题一定要非常非常熟练的拿下！不然就是耻辱。。。

一篇链表题目总结。

/**
     * 从尾到头打印单链表
     * 对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。所以，这一题要么自己使用栈，要么让系统使用栈，也就是递归。注意链表为空的情况
     * 。时间复杂度为O（n）
     */
    public static void reversePrintListStack(Node head) {
        Stack<Node> s = new Stack<Node>();
        Node cur = head;
        while (cur != null) {
            s.push(cur);
            cur = cur.next;
        }

        while (!s.empty()) {
            cur = s.pop();
            System.out.print(cur.val + " ");
        }
        System.out.println();
    }

    /**
     * 从尾到头打印链表，使用递归（优雅！）
     */
    public static void reversePrintListRec(Node head) {
        if (head == null) {
            return;
        } else {
            reversePrintListRec(head.next);
            System.out.print(head.val + " ");
        }
    }