关于判断单链表是否有环代码的分享
vscode写的有些英语单词拼写错误，大家参考参考
#include<stdio.h>
#include<stdlib.h>
typedef struct people{
int numb;
struct people* nuxt;
}people;
//初始化有环的链表：
//自己创建一个有环或者没环的链表
people *create_struct()
{
int size = sizeof(people);
people *a1,*a2,*a3,*a4,*a5,*a6;
a1 = (people *)malloc(size);
a2 = (people *)malloc(size);
a3 = (people *)malloc(size);
a4 = (people *)malloc(size);
a5 = (people *)malloc(size);
a6 = (people *)malloc(size);
a1->nuxt = a2;
a2->nuxt = a3;
a3->nuxt = a4;
a4->nuxt = a5;
a5->nuxt = a6;
a6->nuxt = a3; //这个相当于创建有环
//a6->nuxt = NULL; 这个相当于创建无环
return a1;
}
//判断单链表是否有环
//第一种方法
//第一指针先一步一步走
//第二指针每次第一步开始走
//存在环时 第一指针返回当与第二指针开始相碰时则证明环存在
//传入单链表的头结点指针和 链表长度比如自己上面创建的链表长度为6
int test1(people *test,int lenth)
{
int numb=1;
people *head,*read;
read = head = test;
while(lenth != 0)
{
int buchang=0;
head = test;
read = read->nuxt;
for (int i=0;i<numb;i++)
{
buchang++;
// printf("buchang%d\n",buchang);
// printf("numb%d\n",numb);
//printf("head = %p\n",head);
// printf("read = %p\n",read);
if(head==read && buchang<numb)
{
printf("方法1判断:存在,");
printf("环的节点在%d处\n",buchang);
return 0;
}
head = head->nuxt;
}
numb++;
lenth--;
}
printf("\n方法1判断:不存在\n");
return 1;
}
//第二种快慢指针的方法判断是否有环
//快指针速度是慢指针速度的两倍
//当存在环时 快指针总有一刻会绕到慢指针而后与慢指针相撞则证明环存在
//传入链表头结点指针
int test2(people *test)
{
people *spead1=test,*spead2=test,*test11 = 0;
while (test11 != spead2 )
{
spead1 = spead1->nuxt;
spead2 = spead2->nuxt;
if(spead2==NULL)
{
printf("方法2判断:不存在\n");
return 0;
}
spead2 = spead2->nuxt;
if(spead2==NULL)
{
printf("方法2判断:不存在\n");
return 0;
}
if (spead1 == spead2)
{
printf("方法2判断:存在\n");
return 1;
}
test11 = spead1;
}
}
int main()
{
people *test0;
test0 = create_struct();
test1(test0,6);
test2(test0);
return 0;
}
当：a6->nuxt = NULL;
为无环链表时，
运行结果：
方法1判断:不存在
方法2判断:不存在
当：a6->nuxt = a4;
为有环链表时
运行结果：
方法1判断:存在,环的节点在4处
方法2判断:存在
{:9_223:}
页:
[1]