链表环状检测主要有三种方法:   1、追赶法；如   robinzsy。    2、外部记录法；如improgrammer。    3、内部记录法（打记号）；如VivianSnow。   内部标记法和外部标记法其实是一个道理,不过就是辅助变量一个是在链表节点内,一个是借助辅助数组或者hash或者AVL,红黑树,把已经访问过的节点地址存起来,每次访问下一个时候做查询处理.   追赶法,利用最大公倍数原理,用2个游标,对链表进行访问,例如:p1,p2, p1访问每步向前进1个节点,p2则每次向前前进2个节点,如果有环则p1,p2必会相遇,如果p2先遇到了NULL节点,则说明没有环. 关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣圈可以证明，p2追赶上p1的时候，p1一定还没有走完一遍环路，p2也不会跨越p1多圈才追上我们可以从p2和p1的位置差距来证明，p2一定会赶上p1但是不会跳过p1的因为p2每次走2步，而p1走一步，所以他们之间的差距是一步一步的缩小，4，3，2，1，0 到0的时候就重合了根据这个方式，可以证明，p2每次走三步以上，并不总能加快检测的速度，反而有可能判别不出有环 比如，在环的周长L是偶数的时候，初始p2和p1相差奇数的时候，p2每次走三步，就永远和p1不重合，因为他们之间的差距是：  5， 3 ， 1，  L－1， L－3   如何找到环路的入口? 是这里要重点说明的内容： 解法如下： 当p2按照每次2步，p1每次一步的方式走，发现p2和p1重合，确定了单向链表有环路了.接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当p1和p2再次相遇的时候，就是环路的入口了。这点可以证明的： 在p2和p1第一次相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有 p1走的路径： p+c ＝ n；         c为p1和p2相交点，距离环路入口的距离 p2走的路径： p+c+k*L = 2*N；   L为环路的周长，k是整数 显然，如果从p+c点开始，p1再走n步骤的话，还可以回到p+c这个点, 同时p2从头开始走的话，经过n不，也会达到p+c这点 显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

数据结构-链表环#include<stdio.h>#include<stdlib.h>#define N 3typedef int datatype;typedef struct _node_{    datatype data;    struct _node_ *next;}linknode,*linklist;linklist creat_empty_linklist(){    linklist h;    h = (linklist)malloc(sizeof(linknode));    h->next = NULL;    return h;}int empty_linklist(linklist h){    return NULL == h->next;}int lenth_linklist(linklist h){    int len = 0;    linklist p;    p = h->next;    //p = h;    while(p != NULL)    {        len++;        p = p->next;    }    return len;}void visit_linklist(linklist h){    linklist p;        printf("The linklist is :");    p = h->next;    while(p != NULL)    {        printf("%d->",p->data);        p = p->next;    }    printf("\b\b    \n");        return ;}int insert_linklist_1(linklist h,datatype x,int pos){    int i;    linklist p, q;        p = h;    if((pos < 0) || (pos > lenth_linklist(h)))  return -1;    q = (linklist)malloc(sizeof(linknode));    q->data = http://www.mamicode.com/x;"MY Josephus : ");    for(i=0; i<10; i++){        printf("%d->", p->data);        p = p->next;    }    printf("\b\b    \n");    p = h;    printf("My Josephus out is : ");    while(p != p->next)    {        for(i=0; i<N-2; i++)        {            p = p->next;        }        h = p->next;        p->next = h->next;        printf("%d->", h->data);        free(h);        p = p->next;    }    printf("%d\n", p->data);    return 0;}

求有环单链表中的环长、环起点、链表长求有环单链表中的环长、环起点、链表长1.判断单链表是否有环　　使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。　　就是所谓的追击相遇问题：　　　　2.求有环单链表的环长 　　在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。　　设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：　　　　环长=2*len-len。3.求有环单链表的环连接点位置　　第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。 　　　　　　在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。　　　　第一次相遇时，slow走的长度 S = LenA + x;　　　　第一次相遇时，fast走的长度 2S = LenA + n*R + x;　　　　所以可以知道，LenA + x =  n*R;　　LenA = n*R -x;4.求有环单链表的链表长 　　上述2中求出了环的长度；3中求出了连接点的位置，就可以求出头结点到连接点的长度。两者相加就是链表的长度。 编程实现：　　下面是代码中的例子：　　　　具体代码如下： View Code　　执行结果：本文网址：http://www.cnblogs.com/xudong-bupt/p/3667729.html参考网址：http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html