关于判断单链表是否有环代码的分享

ByTime

vscode写的

有些英语单词拼写错误，大家参考参考

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. typedef struct people{
   
4.     int numb;
   
5.     struct people* nuxt;
   
6. }people;
   
7. 
   
8. //初始化有环的链表：
   
9. //自己创建一个有环或者没环的链表
   
10. people *create_struct()
    
11. {
    
12.     int size = sizeof(people);
    
13.     people *a1,*a2,*a3,*a4,*a5,*a6;
    
14.     a1 = (people *)malloc(size);
    
15.     a2 = (people *)malloc(size);
    
16.     a3 = (people *)malloc(size);
    
17.     a4 = (people *)malloc(size);
    
18.     a5 = (people *)malloc(size);
    
19.     a6 = (people *)malloc(size);
    
20.     a1->nuxt = a2;
    
21.     a2->nuxt = a3;
    
22.     a3->nuxt = a4;
    
23.     a4->nuxt = a5;
    
24.     a5->nuxt = a6;
    
25.     a6->nuxt = a3;        //这个相当于创建有环
    
26.     //a6->nuxt = NULL;   这个相当于创建无环
    
27.     return a1;
    
28. }
    
29. 
    
30. 
    
31. //判断单链表是否有环
    
32. //第一种方法
    
33. //第一指针先一步一步走
    
34. //第二指针每次第一步开始走
    
35. //存在环时   第一指针返回  当与第二指针开始相碰时则证明环存在
    
36. //传入单链表的头结点指针  和 链表长度  比如自己上面创建的链表长度为6
    
37. int test1(people *test,int lenth)
    
38. {
    
39.     int numb=1;
    
40.     people *head,*read;
    
41.     read = head = test;
    
42.     while(lenth != 0)
    
43.     {
    
44.         int buchang=0;
    
45.         head = test;
    
46.         read = read->nuxt;
    
47.         for (int i=0;i<numb;i++)
    
48.         {
    
49.             buchang++;
    
50.            // printf("buchang%d\n",buchang);
    
51.            // printf("numb%d\n",numb);
    
52.           //  printf("head = %p\n",head);
    
53.            // printf("read = %p\n",read);
    
54.             if(head==read && buchang<numb)
    
55.                 {
    
56.                     printf("方法1判断:存在,");
    
57.                     printf("环的节点在%d处\n",buchang);
    
58.                     return 0;
    
59.                 }
    
60.             head = head->nuxt;
    
61.         }
    
62.         numb++;
    
63.         lenth--;
    
64.     }
    
65.     printf("\n方法1判断:不存在\n");
    
66.     return 1;
    
67. }
    
68. 
    
69. 
    
70. //第二种  快慢指针的方法判断是否有环  
    
71. //快指针速度是慢指针速度的两倍
    
72. //当存在环时   快指针总有一刻会绕到慢指针  而后与慢指针相撞则证明环存在
    
73. //传入链表头结点指针
    
74. int test2(people *test)
    
75. {
    
76.     people *spead1=test,*spead2=test,*test11 = 0;
    
77.     while (test11 != spead2 )
    
78.     {
    
79.          
    
80.         spead1 = spead1->nuxt;
    
81.         spead2 = spead2->nuxt;
    
82.         if(spead2==NULL)
    
83.         {
    
84.             printf("方法2判断:不存在\n");
    
85.             return 0;
    
86.         }
    
87.         spead2 = spead2->nuxt;
    
88.         if(spead2==NULL)
    
89.         {
    
90.             printf("方法2判断:不存在\n");
    
91.             return 0;
    
92.         }
    
93.         if (spead1 == spead2)
    
94.         {
    
95.             printf("方法2判断:存在\n");
    
96.             return 1;
    
97.         }   
    
98.         test11 = spead1;
    
99. 
    
100.     }
     
101.    
     
102. }
     
103. 
     
104. int main()
     
105. {
     
106.     people *test0;
     
107.     test0 = create_struct();
     
108.     test1(test0,6);
     
109.     test2(test0);
     
110.     return 0;
     
111. }
     

复制代码

ByTime

当：a6->nuxt = NULL;
为无环链表时，

运行结果：
方法1判断:不存在
方法2判断:不存在





当：a6->nuxt = a4;
为有环链表时

运行结果：
方法1判断:存在,环的节点在4处
方法2判断:存在