ARTS 是什么？

1. Algorithm：Palindrome Linked List

本次練習(xí)的題目是：234. Palindrome Linked List，這個(gè)題目很簡單就是，判斷一個(gè)鏈表是否是回文鏈表。

這個(gè)問題的核心是確定中間節(jié)點(diǎn)，然后再一次對(duì)比兩邊的鏈表，看其是否滿足條件。

確定中間的節(jié)點(diǎn)，這里的思路就是快慢指針，遍歷的時(shí)候一個(gè)指針每次挑一步，另一個(gè)每次跳兩步，這樣當(dāng)快指針走完的時(shí)候，慢指針就在中間附件（要考慮到奇偶性，好的方法就是畫圖舉例）。

解法 1：用 list 存儲(chǔ)

有了上面的想法之后，另一個(gè)要考慮的問題就是，在第一次遍歷的時(shí)候，如果把前半部分的數(shù)據(jù)或結(jié)點(diǎn)存儲(chǔ)下來，而且需要坐下倒序，這樣才能跟后半部分的結(jié)點(diǎn)比較，一開始的想法是使用一個(gè) List 存儲(chǔ)，其實(shí)現(xiàn)如下：

    /**
     * time: O(n), space: O(n), and use list
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome1(ListNode head) {
        boolean ans = true;
        if (head == null) {
            return ans;
        }
        ListNode slowNode = head;
        ListNode quickNode = head;
        if (quickNode.next != null) {
            List<Integer> tmp = new ArrayList<Integer>();
            while (quickNode.next != null && quickNode.next.next != null) {
                tmp.add(slowNode.val);
                slowNode = slowNode.next;
                quickNode = quickNode.next.next;
            }
            // even number
            if (quickNode.next != null) {
                tmp.add(slowNode.val);
            }
            for (int i = tmp.size() - 1; i >= 0; i--) {
                slowNode = slowNode.next;
                if (tmp.get(i) != slowNode.val) {
                    ans = false;
                    break;
                }
            }
        }
        return ans;
    }

時(shí)間復(fù)雜度為 （這里并沒有考慮 list 插入操作的復(fù)雜度），空間復(fù)雜度也是 。

解法 2：原來的鏈表做修改

代碼提交后，發(fā)現(xiàn)這個(gè)解法并不是很好的解法，性能排名比較靠后，就看了性能比較好的解法，它的做法是：直接在原來的鏈表上做修改，改變其指針指向，然后對(duì)比前后鏈表，這樣的空間復(fù)雜度變?yōu)榱?（缺點(diǎn)就是改變了原始鏈表），其實(shí)現(xiàn)如下：

    /**
     * time: O(n), space: O(1), and use ListNode
     * but do some change to original ListNode
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        boolean ans = true;
        if (head == null || head.next == null) {
            return ans;
        }
        ListNode slowNode = head;
        ListNode quickNode = head.next;
        ListNode tmpNode;
        ListNode preNode = null;
        while (quickNode.next != null && quickNode.next.next != null) {
            tmpNode = slowNode;
            slowNode = slowNode.next;
            quickNode = quickNode.next.next;
            tmpNode.next = preNode;
            preNode = tmpNode;
        }
        tmpNode = slowNode;
        slowNode = slowNode.next;
        tmpNode.next = preNode;
        // odd number
        if (quickNode.next != null) {
            slowNode = slowNode.next;
        }
        while (slowNode != null) {
            if (slowNode.val != tmpNode.val) {
                ans = false;
                break;
            }
            slowNode = slowNode.next;
            tmpNode = tmpNode.next;
        }
        return ans;
    }

對(duì)比這兩種解法，性能差異的地方主要是：

1. 空間復(fù)雜度不一樣；
2. 解法 1 使用了 list，如果鏈表非常長，list 需要不斷進(jìn)行擴(kuò)容和遷移數(shù)據(jù)的操作，如果考慮到鏈表的插入消耗，其時(shí)間復(fù)雜度可能為 ，性能不可控。

2. Review

花了兩周時(shí)間，把《Streaming Systems》第一章的內(nèi)容看完了，對(duì)應(yīng)的輸出如下：第一章 Streaming 101（本周的是 Data Processing Patterns 部分）。

3. Tip

極客時(shí)間課程的一個(gè)學(xué)習(xí)總結(jié)：《數(shù)據(jù)結(jié)構(gòu)與算法之美》之?dāng)?shù)組與鏈表。

4. Share

這篇文章還在整理，先拖兩天，盡快補(bǔ)齊。