1.設立2個指針i，j指向頭結點
2.i走1步，j走2步.如果有環，j一定能追上i；
3.如果j不為空，且i和j相等此鏈表即為有環。
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 typedef struct student //定義鏈表結構
5 {
6 int num;
7 struct student *pnext;
8 }stu,*pstu;
9 void link_tail_insert(pstu *phead,pstu *ptail,int i);
10 void link_show(pstu );
11 void link_judge_loop(pstu phead);
12 void main(){
13 pstu phead,ptail;
14 int i;
15 phead = NULL;
16 ptail = NULL;
17 while(scanf("%d",&i) != EOF){
18 link_tail_insert(&phead,&ptail,i);
19 }
20 link_show(phead);
21 ptail->pnext = phead; //單鏈表建立環
22 link_judge_loop(phead);
23 system("pause");
24
25 }
26 void link_tail_insert(pstu *phead,pstu *ptail,int i){ //尾插法建立鏈表
27 pstu pnew;
28 pnew = (pstu)malloc(sizeof(stu));
29 memset(pnew,0,sizeof(stu));
30 pnew->num = i;
31 if(*ptail == NULL){
32 *phead = pnew;
33 *ptail = pnew;
34 }
35 else{
36 (*ptail)->pnext = pnew;
37 *ptail = pnew;
38 }
39 }
40 void link_show(pstu phead){ //輸出鏈表
41 pstu pshow;
42 pshow = phead;
43 if(phead == NULL)
44 {
45 printf("no exsit\n");
46 return;
47 }
48 while(pshow != NULL){
49 printf("%d ",pshow->num);
50 pshow = pshow->pnext;
51 }
52 putchar('\n');
53 }
54 void link_judge_loop(pstu phead){ //判斷是否有環
55 pstu i,j;
56 i = j = phead;
57 while(j != NULL){
58 i = i->pnext;
59 j = j->pnext;
60 if(j == NULL) //j要分步走，判斷是否為空，是空則結束循環
61 break;
62 j = j->pnext;
63 if(i == j) //i和j相等，有環
64 break;
65 }
66 if(j != NULL && i == j)
67 printf("link has loop\n");
68 else
69 printf("link has no loop\n");
70 }
