02.08面试题 环路检测

下面是题目

这题和141.环形链表相近，但是需要考虑更多

有俩个指针 fast ,slow分别的从起点a 开始走，slow走一步，fast走里俩步。如果过程中 快fast走到null,说明不存在环。否则fast和slow一定会相遇，相遇后，slow待在原地不动，将 fast放回原点。然后俩个指针每次都走一步，每次都走一步，每次都走一步。当俩个指针相遇的时候，就是环的入口。

证明：如上图所示，a是起点，b是环的入口，c是俩个指针相遇点，ab之间距离为x，bc之间距离是 y。
当slow 走到 b 时，由于fast 比 slow 走的快，所以fast 已经从 b 开始在环上走了 x 步，可能是多余一圈，距离 b 还差 y 步(解释：我们知道俩个指针相遇的点在c，我们让 slow 退回到b，fast 则会退回 2y 步，所以就是距离b 还差y 步，不会可以画图模拟一下)。知道了 fast 距离 b 还差 y 步，上面知道了 fast 从 b 开始在环上走了 x步。所以环的长度的倍数为 x+y。所以当俩个指针相遇时，把 fast 放回原点，slow 在 c点不动。然后每次都走一步，下一次相遇的时候就是b 点环的入口。

用下面的数学公式比较直观， 相遇的时候， y 走了2*（x+y) , x 走了 （x+y）， x 比y 多走了m个圈圈

（x+y） 2= m cycle+y+x x+y=m cycle m cycle-y=x

/**
 * 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) {
        ListNode *cur1 = head ;//cur1 是快指针
        ListNode *cur2 = head;//cur2 是慢指针
        if(!head||!head->next)//如果头节点就是空，那就直接输出false
            return NULL;
        while(cur1&&cur1->next)
        {
            
            cur1 = cur1->next->next;
            cur2 = cur2->next;
			//相等的时候，我们进行快节点指向头部，慢节点不动，然后一起走的操作
            if(cur1==cur2)
            {
                cur1 = head;
                while(cur1!=cur2)
                {
                   cur1= cur1->next;
                    cur2=cur2->next;
                }
               return  cur2;
            }
        }
         return NULL;
    }
};