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中求出了连接点的位置，就可以求出头结点到连接点的长度。两者相加就是链表的长度。
编程实现：
下面是代码中的例子：
具体代码如下：
1 #include <stdio.h>
2 #include <stdlib.h>
3 typedef struct node{
4 int value;
5 struct node *next;
6 }LinkNode,*Linklist;
7
8 /// 创建链表(链表长度，环节点起始位置)
9 Linklist createList(){
10 Linklist head = NULL;
11 LinkNode *preNode = head;
12 LinkNode *FifthNode = NULL;
13 for(int i=0;i<6;i++){
14 LinkNode *tt = (LinkNode*)malloc(sizeof(LinkNode));
15 tt->value = i;
16 tt->next = NULL;
17 if(preNode == NULL){
18 head = tt;
19 preNode = head;
20 }
21 else{
22 preNode->next =tt;
23 preNode = tt;
24 }
25
26 if(i == 3)
27 FifthNode = tt;
28 }
29 preNode->next = FifthNode;
30 return head;
31 }
32
33 ///判断链表是否有环
34 LinkNode* judgeRing(Linklist list){
35 LinkNode *fast = list;
36 LinkNode *slow = list;
37
38 if(list == NULL)
39 return NULL;
40
41 while(true){
42 if(slow->next != NULL && fast->next != NULL && fast->next->next != NULL){
43 slow = slow->next;
44 fast = fast->next->next;
45 }
46 else
47 return NULL;
48
49 if(fast == slow)
50 return fast;
51 }
52 }
53
54 ///获取链表环长
55 int getRingLength(LinkNode *ringMeetNode){
56 int RingLength=0;
57 LinkNode *fast = ringMeetNode;
58 LinkNode *slow = ringMeetNode;
59 for(;;){
60 fast = fast->next->next;
61 slow = slow->next;
62 RingLength++;
63 if(fast == slow)
64 break;
65 }
66 return RingLength;
67 }
68
69 ///获取链表头到环连接点的长度
70 int getLenA(Linklist list,LinkNode *ringMeetNode){
71 int lenA=0;
72 LinkNode *fast = list;
73 LinkNode *slow = ringMeetNode;
74 for(;;){
75 fast = fast->next;
76 slow = slow->next;
77 lenA++;
78 if(fast == slow)
79 break;
80 }
81 return lenA;
82 }
83
84 ///环起始点
85 ///如果有环, 释放空空间时需要注意.
86 LinkNode* RingStart(Linklist list, int lenA){
87 if (!list || lenA <= 0){
88 return NULL;
89 }
90
91 int i = 0;
92 LinkNode* tmp = list;
93 for ( ; i < lenA; ++i){
94 if (tmp != NULL){
95 tmp = tmp->next;
96 }
97 }
98
99 return (i == lenA)? tmp : NULL;
100 }
101
102 ///释放空间
103 int freeMalloc(Linklist list, LinkNode* ringstart){
104 bool is_ringstart_free = false; //环起始点只能被释放空间一次
105 LinkNode *nextnode = NULL;
106
107 while(list != NULL){
108 nextnode = list->next;
109 if (list == ringstart){ //如果是环起始点
110 if (is_ringstart_free)
111 break; //如果第二次遇到环起始点addr, 表示已经释放完成
112 else
113 is_ringstart_free = true; //记录已经释放一次
114 }
115 free(list);
116 list = nextnode;
117 }
118
119 return 0;
120 }
121
122 int main(){
123 Linklist list = NULL;
124 LinkNode *ringMeetNode = NULL;
125 LinkNode *ringStartNode = NULL;
126
127 int LenA = 0;
128 int RingLength = 0;
129
130 list = createList();
131 ringMeetNode = judgeRing(list); //快慢指针相遇点
132
133 if(ringMeetNode == NULL)
134 printf("No Ring\n");
135 else{
136 printf("Have Ring\n");
137 RingLength = getRingLength(ringMeetNode); //环长
138 LenA = getLenA(list,ringMeetNode);
139
140 printf("RingLength:%d\n", RingLength);
141 printf("LenA:%d\n", LenA);
142 printf("listLength=%d\n", RingLength+LenA);
143 }
144
145 ringStartNode = RingStart(list, LenA); //获取环起始点
146 freeMalloc(list, ringStartNode); //释放环节点, 有环时需要注意. 采纳5楼建议
147 return 0;
148 }
View Code
执行结果：
本文网址：http://www.cnblogs.com/xudong-bupt/p/3667729.html
参考网址：http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html