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;

    }

};

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

巴特西

3月2日 Linked List Cycle

最新文章

热门文章