[142. circular linked list II]

---

One 、 Title Description

Topic link

---

Two 、 How to do it

Train of thought ： Formula proof

Train of thought two ： When you don't know the derived formula
You must be in the circle when you meet , It is the tail node
Do it with the idea of intersecting linked lists

Train of thought three ：

---

3、 ... and 、 Title code

Train of thought ： Formula proof

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    struct ListNode * meet = NULL;
    while(fast && fast->next)
    {
    
        fast=fast->next->next;
        slow=slow->next;
        if(fast == slow)
        {
    
            meet = fast;
           while(head != meet)
           {
    
             head=head->next;
             meet=meet->next;
           }
           return meet;
        }
    }
    return NULL;
}

Train of thought two ：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB,struct ListNode *tail) {
    
    struct ListNode * listA = headA;
    struct ListNode * listB = headB;
    int lenA=1;int lenB=1;
    while(listA!=tail)
    {
    
        listA=listA->next;
        lenA++;
    }
    while(listB!=tail)
    {
    
        listB=listB->next;
        lenB++;
    }
    if(listA != listB)
    {
    
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode * longlist = headA;
    struct ListNode * shortlist = headB;
    if(lenA < lenB)
    {
    
        longlist = headB;
        shortlist = headA;
    }
    while(gap--)
    {
    
        longlist=longlist->next;
    }
    while(longlist != shortlist)
    {
    
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return shortlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    struct ListNode * meet = NULL;
    while(fast && fast->next)
    {
    
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
    
            meet=slow;
            struct ListNode * newhead = meet->next;
            struct ListNode * p=getIntersectionNode(newhead,head,meet);
            return p;
        }
    }
   return NULL;
}

Train of thought three ：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    struct ListNode * listA = headA;
    struct ListNode * listB = headB;
    int lenA=1;int lenB=1;
    while(listA->next)
    {
    
        listA=listA->next;
        lenA++;
    }
    while(listB->next)
    {
    
        listB=listB->next;
        lenB++;
    }
    if(listA != listB)
    {
    
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode * longlist = headA;
    struct ListNode * shortlist = headB;
    if(lenA < lenB)
    {
    
        longlist = headB;
        shortlist = headA;
    }
    while(gap--)
    {
    
        longlist=longlist->next;
    }
    while(longlist != shortlist)
    {
    
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return shortlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    struct ListNode * meet = NULL;
    while(fast && fast->next)
    {
    
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
    
            meet=slow;
            struct ListNode * newhead = meet->next;
            meet->next=NULL;
            struct ListNode * p=getIntersectionNode(newhead,head);
            return p;
        }
    }
   return NULL;
}

---

The above is the whole content of this article , If there are mistakes in the article or something you don't understand , Communicate more with meow bloggers . Learn from each other and make progress . If this article helps you , Can give meow bloggers a concern , Your support is my biggest motivation .