给定一个单链表，只给出头指针h：
- 如何判断是否存在环？
- 如何知道环的长度？
- 如何找出环的连接点在哪里？
- 带环链表的长度是多少？
问题1 如何判断是否有环
使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
slow fast
问题2 如何判断环的长度
在相遇点出同时出发，fast指针和slow指针再次相遇时，slow指针走过的点的个数就是环的长度。试问会不会slow在不到一圈的地方两者相遇呢？不会，因为假设slow走s,则fast走2s。二者相遇则二者距离必相差圈数的倍数，即：2s-s = k*圈距离=s。此时k=1。因此得出结论：从相遇到再次相遇，slow再走完整的一圈。
问题3 如何找出环的连接点
定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。
证明：
链表形状类似数字6。 假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。 则总长度（也是总结点数）为 a+b 。 从头开始，0 base 编号。 将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ... 当 i＜a 时，S(i)=i ； 当 i≥a 时，S(i)=a+(i-a)%b 。
分析追赶过程。 两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x) 由环的周期性有：2x=tb+x 。得到 x=tb 。 另，碰撞时，必须在环内，不可能在甩尾段，有 x>=a 。
连接点为从起点走 a 步，即 S(a)。 S(a) = S(tb+a) = S(x+a)。 得到结论：从碰撞点 x 前进 a 步即为连接点。
根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而 S(x+a) 必然在环上。所以可以发生碰撞。 又，同为前进 a 步，同为连接点，所以必然发生碰撞。
综上，从 x 点和从起点同步前进，第一个碰撞点就是连接点。
问题4 带环链表的长度是多少
问题2知道环的长度，问题3知道环外边的长度。两者相加即为总长度。
参考代码
#include#include typedef struct node{ int data; struct node *next;}node;node *Create_list() //建立链表{ node *p_return, *p; p_return = NULL; node *n1 = (node *)malloc(sizeof(node)); n1->data = 1; n1->next = NULL; p = n1; p_return = p; node *n2 = (node *)malloc(sizeof(node)); n2->data = 2; n2->next = NULL; p->next = n2; p = n2; node *n3 = (node *)malloc(sizeof(node)); n3->data = 3; n3->next = NULL; p->next = n3; p = n3; node *n4 = (node *)malloc(sizeof(node)); n4->data = 4; n4->next = NULL; p->next = n4; p = n4; node *n5 = (node *)malloc(sizeof(node)); n5->data = 5; n5->next = NULL; p->next = n5; p = n5; node *n6 = (node *)malloc(sizeof(node)); n6->data = 6; n6->next = NULL; p->next = n6; p = n6; p->next = n3; return p_return;}node *find_in_node(node *p1, node *p2) //找到入环的结点{ while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1;}int get_out_len(node *p1, node *p2) //计算出环外边的长度{ int num = 0; while(p1 != p2) { p1 = p1->next; p2 = p2->next; num++; } return num;}node *check_loop(node *p) //检查是否有环{ node *p_slow, *p_fast; p_slow = p; p_fast = p; int tag = 0; while(p_slow && p_fast->next) { p_slow = p_slow->next; p_fast = p_fast->next->next; if(p_slow == p_fast) { tag = 1; break; } } if(tag == 1) { printf("Have loop\n"); return p_slow; } else { printf("Not have loop\n"); return NULL; }}int get_len_loop(node *var_loop) //得出环的长度{ node *p = var_loop->next; int num = 1; while(p != var_loop) { p = p->next; num++; } return num;}int main(){ node *p = Create_list(); node *coin_loop = check_loop(p); if(coin_loop) { int len_loop = get_len_loop(coin_loop); printf("Length of Loop is:%d\n", len_loop); node *in_node = find_in_node(p, coin_loop); int len_out = get_out_len(p, coin_loop); printf("Length of out Loop is %d\n", len_out); printf("Length of all is %d\n", len_out + len_loop); }}