判断一个单链表是否有环及环长和环的入口点

判断是否有环

常用方法：追赶法，即设两个指针q与 p，都从头结点出发，一个一次两个结点，q=q->next->next,一个一次一个结点，p=p->next,如果q==NULL或p==NULL则单链表无环；如果q==p则单链表有环；注意需要判断q->next==NULL是否成立；

{
    node *q,*p;
    p=q=head->next;
    if (q!=NULL&&q->next!=NULL)
    {
            p=p->next;
            q=q->next->next;
    }
    while (q!=NULL&&q->next!=NULL)
    {
        if (q!=p)
        {
            p=p->next;
            q=q->next->next;
        }
        else{
            return 1;
        }
    }
    return 0;
} ```


## 环长
```  //返回有环链表的环长 
int length(linklist head)
{
    int begin=0,again=0,length=0;
    node *fast=head,*slow=head;
    while (fast!=NULL&&fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    
        if (fast==slow&&again==1)//特别注意一下这里的顺序，若把第一个if与第二个if调换有错误。 
        {
            break;
        }
        if (fast==slow&&again==0)
        {
            begin=again=1;
        }
        if (begin==1)
        {
            ++length;
        }
    } 
//  printf("\n%d %d\n",begin,again);
    return length;
} 

入口点位置

node *Entraence(linklist head)
{
    node *fast=head->next,*slow=head->next;
    while (fast!=NULL&&fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
        if (fast==slow)
        {
            break;
        }
    }
    slow=head->next;
    while (slow!=fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return fast;
}