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

ByTime

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;
}

ByTime

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

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





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

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