力扣 141.环形链表和142.环形链表2

1.环形链表Ⅰ解题思路

利用快慢指针，快指针一次走两个，慢指针一次走一个，如果出现了快指针为空或者快指针的next为空的现象则说明不带环，但如果带环，那么快指针就一定能够追上慢指针，原理如下在这里插入图片描述

2.环形链表Ⅰ代码实现

bool hasCycle(struct ListNode *head)
 {  if(head==NULL)
    return false;
     if(head->next==NULL)
     return false;
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast)
    {   if(fast->next==NULL)
        return false;
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow&&fast!=NULL)
        return true;
    }
return false;
}

3.环形链表Ⅱ解题思路

首先利用环形链表Ⅰ的思路可以求出快慢指针相遇时指针的位置则可设此位置距离循环开始的位置距离为X，设从开头到循环点的距离为L，环的长度为C,则慢指针走的路程就为L+X，而且快指针走的距离就为L+n*C+X，则由数学公式推理可得：一个指针从相遇点走，另一个指针从开头走，则他们会在循环入口点相遇，由此特性就可得出循坏的开始点.

在这里插入图片描述

4.环形链表Ⅱ代码实现

struct ListNode *detectCycle(struct ListNode *head) 
{   
     if(head==NULL)
    return NULL;
     if(head->next==NULL)
     return NULL;
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast)
    {   if(fast->next==NULL)
        return NULL;
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow&&fast!=NULL)
        break;
    }
    if(fast==NULL)
    return NULL;
  struct ListNode *p=head;
    while(p!=fast)
    {
fast=fast->next;
p=p->next;

    }
return fast;

}