【数据结构篇】~链表算法题3（环形链表）

环形链表的证明

1. 环形链表I​

https://leetcode.cn/problems/linked-list-cycle/description/

1) 思路

判断链表是否带环，还是要使用快慢双指针，如果带环那他们一定在环中相遇，如果没带环那么就返回false

2）代码实现

typedef struct ListNode ls;
bool hasCycle(struct ListNode *head) {
    ls*slow=head,*fast=head;
    //开始循环
    while(fast && fast->next)//分为奇数偶数两种情况所以要fast&&fast->next
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        return true;
    }
    return false;   
}

2. 环形链表II​

https://leetcode.cn/problems/linked-list-cycle-ii/description/​

1) 思路1

找到相遇节点，然后把相遇节点的next指针置为newnode，再把meet->next置为空，这时再找入环节点就可以转化为找相交链表的相交节点

1) 思路2

找到相遇节点后然后开时循环，让相遇节点和头节点同时同步走，直到两个指针相遇时，就找到了入环节点

2）代码实现

typedef struct ListNode lsnode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    lsnode*l1=headA;
    lsnode*l2=headB;
    int sizea=0;int sizeb=0;
    while(l1)
    {
       ++sizea;
        l1=l1->next;      
    }
    while(l2)
    {
        ++sizeb;
        l2=l2->next;     
    }
    //计算a和b的长度，让长的先走差值步，到同一起点上
     lsnode* plong = headA;
    lsnode* pshort = headB;
    if(sizeb>sizea)
    {
        plong= headB;
        pshort=headA;
    }
    

    int gap=abs(sizea-sizeb);
    while(gap--)
    {
        plong = plong -> next;
    }
    //开始比较
    while(plong && pshort)
    {
        //这里比较地址，如果比较值得话有问题
        if(plong == pshort)
       { 
        return pshort;
       }
       //同步走
        plong=plong->next;
        pshort=pshort->next;    
    }
    return NULL;   
}
struct ListNode *detectCycle(struct ListNode *head) 
{
    lsnode*slow=head,*fast=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            lsnode*meet=slow;//相遇节点
            lsnode*newhead=meet->next;
            meet->next=NULL;//变为了相交链表找相交节点
            return getIntersectionNode(head,newhead);
        }       
    }  
     return NULL;
}

```c
typedef struct ListNode  lsnode;
struct ListNode *detectCycle(struct ListNode *head) 
{
     lsnode*slow=head,*fast=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            lsnode*meet=slow;//相遇节点
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }      
    }  
     return NULL;   
}