环形链表问题-ag真人游戏

问题描述：
给定一个链表，判断链表中是否有环。

首先介绍一下快慢指针：
我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。
来看以下例子：

在环形链表问题中，我们用slow和fast指向链表的开始，slow一次走一步，fast一次走两步。若不带环，fast就会为空，带环，fast就会在环内追上slow

1.我们先来证明为什么slow和fast一定会在环中相遇。

1. fast先进环，这时slow走了入环前距离的一半。
2. 随着slow进环，fast在环内走了一段，但走了多少跟环的大小有关。
3. 假设slow进环时，与fast之间的距离是n，fast开始追slow。slow每次往前走一步，fast往前走两步。所以fast和slow的距离变化：
   n -> n-1 -> n-2 … 1 -> 0
   每追一次，距离就减1，他们之间的距离减到0的时候就是相遇的点。

那么如何求环的入口点呢？
追上相遇的过程中：

1. slow走的距离：l x
   fast走的距离：l n* c x (n>=1)
   (n是相遇前，fast在环内走的圈数)
2. 2*（l x) = l n* c x
   得到：l=(n-1)* c c-x
3. 其中，(n-1)* c相当于从相遇点又走回到相遇点，没有变化， c-x 相当于从相遇点到相交点（顺时针）的距离。

结论： 一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇。

代码实现：

struct listnode *detectcycle(struct listnode *head) {
  
    struct listnode* slow=head,*fast=head;
    while(fast && fast->next)
    {
  
        slow=slow->next;
        fast=fast->next->next;
        if(slow == fast)
        {
  
            //相遇
            struct listnode* meet=slow;
            while(meet != head)
            {
  
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return null;
}

或者我们可以转换成链表相交的问题，即令相遇点的下一个结点为另一个链表头，这里不再细讲。

延伸问题：证明fast一次走n步时，即n>2时不一定会在环中相遇。

假设slow一次走1步，fast一次走3步，slow进环后，fast和slow之间的距离为n，fast开始追slow。
他们之间的距离变化如下：

1. n是偶数：
   n -> n-2 -> n-4 … 2 -> 0
   n是偶数时可以追上

2. n是奇数：
   n -> n-2 -> n-4 … 1 -> -1
   n是奇数时，将会错过

如果n是奇数，距离变为-1，即意味着他们之间的距离变为c-1(c是环的长度）
如果c-1也是奇数，那么就永远追不上了，
如果c-1是偶数，就可以追上。

假设slow一次走1步，fast一次走n步的推导过程与之类似。