学步园

判断一个链表是否有环的最简单方式是为每个遍历的节点打一个标记，这样最多需要N次遍历就可以判断链表是否存在环。

如果存储有限或节点不能更改，可以参照寻找节点倒数第N个节点的方式进行判断，就是设置一个快节点ptr_fast，一个慢节点ptr_slow，ptr_fast先行遍历，ptr_slow在ptr_fast后相距一个节点开始遍历，当ptr_fast和ptr_slow相遇时证明链表含有节点。原理如下：

设链表中非回环的节点数为m，回环中节点数是n，设前后两个指针遍历的步长分别是x，y，如果有环，经过t次移动ptr_slow和ptr_fast必然会在回环内相遇，这是小学数学中最常见的追逐问题，则有以下方程式：

xt - yt = pn（p为在环中跑了几圈）

这个方程需要有一个限制条件，那就是必须在慢指针进入环的情况下才能成立yt > m，如果让算法的效率最高，那么就要指针移到的次数最少，

t = pn /(x - y) * t &&  t > m / y

若想让pn永远整除x-y，那么x-y = 1永远满足条件，也就是说ptr_slow和ptr_fast保持一个节点的距离就可以保证两个节点在环内相遇（在环存在的情况下）

int IsLoop(link_list *head)
{
    link_list *ptr_slow= head, *ptr_fast = head;

    while ( ptr_fast && ptr_fast ->next ) 
    {
        ptr_slow= ptr_slow->next;
        ptr_fast = ptr_fast ->next->next;
        if ( ptr_fast == ptr_slow ) break;
    }
    if(fast == NULL || fast->next == NULL){
         return 0;
    }else{
         return 1
    }
}

至于如何找到环的入口点，可以在相遇点和链表头分表设置一个指针，两个指针每次移动一步，当两个指针相遇就是环的入口点

/*************************************************************************
        > File Name: cicle.c
        > Author: desionwang
        > Mail: wdxin1322@qq.com 
        > Created Time: Thu 14 Nov 2013 02:32:21 PM CST
 ************************************************************************/

#include<stdio.h>
link_list* IsLoop(link_list *head)
{
        link_list *ptr_slow= head, *ptr_fast = head;

        while ( ptr_fast && ptr_fast ->next ) 
        {
                ptr_slow= ptr_slow->next;
                ptr_fast = ptr_fast ->next->next;
                if ( ptr_fast == ptr_slow ) break;
        }
        if(fast == NULL || fast->next == NULL){
                 return NULL;
        }
        ptr_slow = head;
        while(ptr_slow != ptr_fast){
                ptr_slow= ptr_slow->next;
                ptr_fast = ptr_fast ->next
        }
        return ptr_slow;
}