判断单链表是否环化和寻找环的起点

我们可以使用一对"快慢指针",快指针每次走两步,慢指针每次走一步,同时从起点出发,依次向后遍历链表,如果两个指针相遇则一定存在环,如果不能相遇则不存在环

 LNode *fast=L->next,*slow=L->next;//使用快慢指针
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;//快指针每次走两步,慢指针每次走一步
        if(slow==fast)break;//在x处相遇相遇
    }
    if(slow==NULL||fast->next==NULL)return NULL;//判断是否环化

#include 
#include 
#include

typedef int Elemtype;

typedef struct LNode
{
    Elemtype data;
    struct  LNode *next;
} LNode,*LinkList;




LinkList List_TailInsert(LinkList L)
{
    int x;
    L=(LinkList)malloc(sizeof(LinkList));//创建头节点
    L->next=NULL;

    LNode *r=L,*s;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode*)malloc(sizeof(LNode*));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=L->next; //使环化
    return L;
}



void PrintLinkList(LinkList L)
{
    printf("打印链表n");
    LNode *r=L->next;
    while(r!=NULL)
    {
        printf("%d--->",r->data);
        r=r->next;
    }
    printf("n");
}


LNode * FindLoopStart(LinkList L)
{
    LNode *fast=L->next,*slow=L->next;//使用快慢指针
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;//快指针每次走两步,慢指针每次走一步
        if(slow==fast)break;//在x处相遇相遇
    }
    if(slow==NULL||fast->next==NULL)return NULL;//判断是否环化

    LNode *p1=L->next,*p2=slow;//p2为相遇点
    while(p1!=p2)
    {
        p1=p1->next;
        p2=p2->next;
    }
    return p1;
}


int main()
{

    LinkList L;//头指针,创建链表
    printf("创建链表,输入链表的值 9999表示结束!n");
    L=List_TailInsert(L);
    printf("链表环起点的值为  %dn",FindLoopStart(L)->data);

    return 0;
}