3月2日 Linked List Cycle

今天星期天，准备好周一的PPT内容，再回来做题，以后考虑周末做一个APP或者微信帐号玩吧。

回到题目， Linked List Cycle，一个检查单项链表是否有环路的问题。

题目周五的时候就简单做过，可是链表中带入了一个val常量，当时误以为是要检查是否有重复值，WA了。

早上再试了会，缓过来，其实还是比较地址指针。

最开始写的一个简单方法，只能判断是否与头指针重复，但是如果环路从中间开始就判断不到了，再想了10多分钟，有一个O(n^2)的算法，每次从第一个指针开始，判断后面k-1个指针是否相同：

/**
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL) return false;
        if (head->next == NULL) return false;
        //if (head->val == head->next->val) return true;
        
        ListNode *p = head->next;
        int counter = 1;
        
        while (p != NULL)
        {
            //if (p->val == head->val) return true;
            ListNode *cpr = head;
            
            for (int i = 0; i < counter; ++i)
            {
                if (cpr == p) return true;
                cpr = cpr->next;
            }
            
            p = p->next;
            counter++;
        }
        return false;
    }
};

可惜，TLE超时了，看了下用例，最大长度已经超过5000，5000的平方已经超过2千5百万，确实是超过1秒了。

后续又思考了半个多小时，画满了一张草稿纸也没想好，囧，战斗力下滑啊。

看了Discuss里，一句话就明白了，一个跑得快，一个跑得慢，两个相遇的时候就是环路了。

所以就有了下面的做法，写的比较快，所以加了if多一点：

/**
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL) return false;
        if (head->next == NULL) return false;
        if (head->next->next == NULL) return false;
        
        ListNode *p = head->next;
        ListNode *p2 = head->next->next;
        
        while (p != NULL && p2 != NULL)
        {
            if (p == p2) return true;
            if (p2->next == NULL) return false;
            if (p2->next->next == NULL) return false;
            p = p->next;
            p2 = p2->next->next;
        }
        return false;
    }
};

下次遇到类似的问题，考虑从反方向思考。