概述

  Floyd判圈算法又称作是龟兔赛跑算法，就是快慢指针的应用，主要用于判断并找到环形链表的入口。做法是设置两个指针，一个快指针（兔子），一个慢指针（乌龟），快指针一次移动两个节点，慢指针一次移动一个节点。如果有环存在，它们第一次会在环上相遇，这时快指针移动到出发点，转换成慢指针（就是以慢指针的速度移动），两指针再同时移动，每次移动一个节点，再次相遇时，会在环的入口处。

证明

  主要有两点需要证明：

1. 兔子和乌龟在环内必然相遇。
2. 兔子和乌龟再次相遇时，在环的入口处。

  对于第一点的证明很简单，如果环存在，当乌龟到环入口时，兔子已在环内某节点处，它们之间存在一定距离（包括相遇），又存在固定的速度差，这就是简单的相遇问题了（追及问题），所以必然会在环内某点相遇。

  对于第二点的证明，要分为两个要点:

1. 兔子（速度和乌龟一样了）和乌龟会再次相遇
2. 相遇点在入口处

  先证明第一点，假设第一次相遇时，兔子走的2n个节点，则乌龟走了n个节点。兔子从出发点再次回到相遇点时，走了n个节点，与上一次乌龟走的一样，这时乌龟又走了n个节点，一共走了2n个节点，与上一次相遇时兔子走的一样，这时则也必然回到相遇点，两者相当于身份转换了。

  对于第二点的证明，因为两者的速度一样了，所以在环内，相遇的话，上个节点也必然相遇，若不相遇，则都不会相遇，那么它们第二次只可能在环的入口处相遇，才能保证处处相遇。

实现

  通用代码如下：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

  

        if(head == NULL) {

            return NULL;

        }

  
		//分配空间并初始化
        ListNode* fhead = new ListNode(0);

        fhead->next = head;

		//将快慢指针初始在链表外，为下一个循环判断做准备
        ListNode* fast = fhead;

        ListNode* slow = fhead;

  
		//判断是否存在环
        do {
			//链表到头了，说明是单向链表
            if(fast->next == NULL || fast->next->next == NULL) {
				//释放内存，防止内存泄漏
                delete fhead;

                return NULL;

            }

  
			//快指针一次移动两个节点
            fast = fast->next->next;
			//慢指针一次移动一个节点
            slow = slow->next;

        } while(fast != slow);

  

        fast = fhead;

  
		//找到环的入口
        while(fast != slow) {

            fast = fast->next;

            slow = slow->next;

        }

  

        ListNode* result = fast;
		//释放内存，防止内存泄漏
        delete fhead;

  

        return result;

    }

};

例题

  这里有相关例题，可以练习练习：

1. 141. 环形链表 - 力扣（LeetCode）
2. 142. 环形链表 II - 力扣（LeetCode）
3. 287. 寻找重复数 - 力扣（LeetCode）