[数据结构与算法]环形链表问题

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

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

在环形链表问题中，我们用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步的推导过程与之类似。