leetcode 好题 01 -- floyd 判圈算法
19 February 2018
原文: 判圈算法(Flyod、Brent's)

介绍

leetcode 141. Linked List Cycle

判断一个链表是否有环(不止是首尾有环,链表的中间部分也可能出现环)

<img class="org-img img-responsive" src="/images/algo/floyd-cycle-detect-1.jpg"/>

Floyd cycle detection(龟兔算法)

对于赛道来说,如果赛道中有环,那么速度快的兔子一定会在某个地点追上乌龟,并且兔子所跑的距离减去乌龟所跑的距离,一定是环长度的整数倍。

原理

假设令龟、兔为指针,并且指向起点位置,兔子每次移动两个节点,乌龟每次移动一个节点。如果两者在起始节点外相遇,则说明有环。如果兔子在走到链表尾部还没有与乌龟相遇,说明无环。

环长度

通过上述算法判断出存在环 C 时,显然龟兔位于同一节点 M,此时,令兔子保持不动,而乌龟不断推进,记录移动距离,等再次相遇时,移动步数即环 C 长度。

环起点

只要令兔子仍位于相遇节点 M, 而令乌龟返回链表起始节点 S,此时乌龟与兔子之间的距离为环 C 长度的整数倍。随后,同时让乌龟与兔子不断推进一步,直至相遇同一节点 P,则节点 P 即为从链表起始节点所到达的环 C 的第一个节点,即环 C 起点。

分析

如图所示,令起始节点为 h, 起始节点到环起点距离为 m, 龟兔相遇节点为 p,p 节点与环起点距离为 n;
当龟兔相遇时
乌龟所跑距离为 S = m + n + aC (C 为环长度),
兔子所跑距离为 2S = m + n + bC (因为兔子速度为乌龟 2 倍)
故得 S = (b - a)C = m + n + aC ==> (b - 2a)C = m + n , 由此可知,m + n 为环 C 长度整数倍.
那么令乌龟返回链表起始节点,兔子仍在相遇节点 P,两者同时不断推进直至相遇,相遇节点为环起点。因为乌龟移动距离 m, 则兔子也移动距离 m, 原本 p 节点距离环起点为 n, 由于 m + n 为环长整数倍,故兔子移动到了环起点,即相遇节点为环起点。

<img class="org-img img-responsive" src="/images/algo/floyd-cycle-detect-2.png"/>

代码

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;

        bool hasCircle = true;

        do {
            if (fast == NULL || fast->next == NULL) {
                hasCircle = false;
                break;
            }
            fast = fast->next->next;
            slow = slow->next;
        } while (fast != slow);

        return hasCircle;
    }
};