有环单链表需要解决的问题：

1、如何判断有环没有环？

使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。

2、如何判断环的长度？

记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞slow所走过的操作数就是环的长度s

3、如何找到环的连接点在哪里？

有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

4、如何求带环单链表的长度？

问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度

1. #include<iostream>  
2. using namespace std;  
3. struct Node  
4. {  
5.     int data;  
6.     Node *next;  
7. };  
8.  
9. //判断是否有环  
10. Node* CircleExist(Node *head)  
11. {  
12.     Node *slow=head;  
13.     Node *fast=head;  
14.     while(fast!=NULL&&fast->next!=NULL)  
15.     {  
16.         slow=slow->next;  
17.         fast=fast->next->next;  
18.         if(slow==fast)  
19.             return slow;  
20.     }  
21.     return NULL;  
22. }  
23.  
24. //得到环的长度  
25. int GetCircleLength(Node *slow)  
26. {  
27.     int length=1;  
28.     Node *fast=slow;  
29.     slow=slow->next;  
30.     fast=fast->next->next;  
31.     while(fast!=slow)  
32.     {  
33.         slow=slow->next;  
34.         fast=fast->next->next;  
35.         length++;  
36.     }  
37.       
38.     return length;  
39. }  
40. //得到环的连接点  
41. int GetConnectPoint(Node *head,Node *slow,int &count)  
42. {  
43.     count=0;  
44.     while(head!=slow)  
45.     {  
46.         head=head->next;  
47.         slow=slow->next;  
48.         count++;  
49.     }  
50.     return slow->data;  
51. }  
52. void main()  
53. {  
54.     Node list[8];  
55.     for(int i=0;i<8;i++)  
56.         list[i].data=i;  
57.     list[0].next=&list[1];  
58.     list[1].next=&list[2];  
59.     list[2].next=&list[3];  
60.     list[3].next=&list[4];  
61.     list[4].next=&list[5];  
62.     list[5].next=&list[6];  
63.     list[6].next=&list[7];  
64.     list[7].next=&list[2];  
65.     Node *c=CircleExist(&list[0]);  
66.     if(c!=NULL)  
67.         cout<<"有环！\n";  
68.     else 
69.     {  
70.         cout<<"无环！\n";  
71.         return;  
72.     }  
73.     int circlelength=GetCircleLength(c);  
74.     cout<<"环的长度："<<circlelength<<endl;  
75.     int count=0;  
76.     cout<<"环的连接点:"<<GetConnectPoint(&list[0],c,count)<<endl;  
77.     cout<<"链表总长度:"<<count+circlelength<<endl;  
78. }