ARTS 第2周（20190401~20190407）

ARTS 是什么？

1. Algorithm：Palindrome Linked List

本次练习的题目是：234. Palindrome Linked List，这个题目很简单就是，判断一个链表是否是回文链表。

这个问题的核心是确定中间节点，然后再一次对比两边的链表，看其是否满足条件。

确定中间的节点，这里的思路就是快慢指针，遍历的时候一个指针每次挑一步，另一个每次跳两步，这样当快指针走完的时候，慢指针就在中间附件（要考虑到奇偶性，好的方法就是画图举例）。

解法 1：用 list 存储

有了上面的想法之后，另一个要考虑的问题就是，在第一次遍历的时候，如果把前半部分的数据或结点存储下来，而且需要坐下倒序，这样才能跟后半部分的结点比较，一开始的想法是使用一个 List 存储，其实现如下：

    /**
     * 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;
    }

时间复杂度为 （这里并没有考虑 list 插入操作的复杂度），空间复杂度也是 。

解法 2：原来的链表做修改

代码提交后，发现这个解法并不是很好的解法，性能排名比较靠后，就看了性能比较好的解法，它的做法是：直接在原来的链表上做修改，改变其指针指向，然后对比前后链表，这样的空间复杂度变为了 （缺点就是改变了原始链表），其实现如下：

    /**
     * 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;
    }

对比这两种解法，性能差异的地方主要是：

1. 空间复杂度不一样；
2. 解法 1 使用了 list，如果链表非常长，list 需要不断进行扩容和迁移数据的操作，如果考虑到链表的插入消耗，其时间复杂度可能为 ，性能不可控。

2. Review

花了两周时间，把《Streaming Systems》第一章的内容看完了，对应的输出如下：第一章 Streaming 101（本周的是 Data Processing Patterns 部分）。

3. Tip

极客时间课程的一个学习总结：《数据结构与算法之美》之数组与链表。

4. Share

这篇文章还在整理，先拖两天，尽快补齐。