用途

Floyd Cycle Detection Algorithm，是一个可以在有限状态机、迭代器或者链表上判断时候有环的算法，同时还可以得出环的起点与长度的算法。

思路

判断是否有环

Floyd Cycle Detection Algorithm 有点类似于龟兔（我和别人在操场上）赛跑（跑步）。假如说赛道有环，那么最终跑得慢的（我）会被跑得快的（别人）套圈。如果别人成功跑到了终点，那么就没有环，如果我和别人在路上相遇了，就说明我被他套圈了，赛道是有环的，同时，他比我多跑的长度是环的长度的整数倍。

求环的长度

第一次相遇的时候，两个人都已经在环上了。两个人继续跑的话，在下一次相遇时候，快的人一定比慢的人多跑了一整圈。在第一次相遇和第二次相遇之间，快的人跑的比慢的人多跑了一整圈，也就是多跑了环的长度。

确定环的起点

这儿以链表为例，同时要求快指针是慢指针速度的两倍（快指针每次走一步，慢指针每次走两步）。

首先，快慢指针在链表上移动，直到第一次相遇。之后将快指针移动到链表的开头，以慢指针的速率进行移动。当快指针和慢指针又一次相遇时，相遇的地点就是环的起点。

假设第一次相遇时候，慢指针在进入环之前走了 a 长度，在环上走了 b 长度，那么快指针在进入环之前走了 a 长度，在环上走了 a + 2 * b 的长度，并且，a + b 是环长度的整数倍。

第一次相遇后，快指针被移动到开头，并且速度设置到和慢指针相同。第一次相遇后，快指针走了 a 长度（打到环的起点时候），慢指针也走了 a 长度，由于 a + b（b 指的是块指针第二次出发时候，慢指针已经走的长度）是环长度的整数倍，所以此时慢指针也到达了环的开头，与快指针相遇。

由于在此之前，快慢指针都不可能相遇，所以，快慢指针第二次相遇的位置就是环的起点。

例子

LeetCode 202：快乐数。这儿是在迭代器上判断是否有环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool isHappy(int n) {
        int fast = n, slow = n;
        do {
            fast = next(next(fast));
            slow = next(slow);
        } while (fast != slow);
        return fast == 1;
    }

private:
    int next(int n) {
        int result = 0;
        while (n != 0) {
            int val = n % 10;
            result += val * val;
            n /= 10;
        }
        return result;
    }

};

LeetCode 142：环形链表2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
  public ListNode detectCycle(ListNode head) {
    if (head == null)
      return null;
    
    ListNode p = head, p2 = head;
    boolean hasCycle = false;
    while (p.next != null && p2.next.next != null) {
        p = p.next;
        p2 = p2.next.next;
        if (p == p2) {
            hasCycle = true;
            break;
        }
    }
    
    if (hasCycle) {
        ListNode q = head;
        while (p != q) {
            p = p.next;
            q = q.next;
        }
        return q;
    } else 
        return null;
  }
}