[speed pointer] 142 circular linked list II

One 、 subject

Given a linked list , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list .

No modification allowed Linked list .

Example 1：

Input ：head = [3,2,0,-4], pos = 1
Output ： The return index is 1 The linked list node of
explain ： There is a link in the list , Its tail is connected to the second node .
Example 2：

Input ：head = [1,2], pos = 0
Output ： The return index is 0 The linked list node of
explain ： There is a link in the list , Its tail is connected to the first node .
Example 3：

Input ：head = [1], pos = -1
Output ： return null
explain ： There are no links in the list .

Two 、 Answer key

For the link list to find the loop problem , There is a general solution —— Fast and slow pointer method ：
Given that both pointers point to the starting point , One for fast pointer , Move two steps at a time ; One is a slow pointer , One step at a time . If the fast pointer can go to the end , Explain the Fifth Ring Road , Otherwise there is a loop .
After confirming that there is a loop , How to find the starting point of the loop ？

• First, when determining the loop , The end condition is that the speed pointer meets for the first time
• Then the fast pointer is reset to the starting point , Slow hands don't move , When moving the second time, the fast and slow pointer moves only one step each time , Until the second meeting , At this time, the point of meeting is the starting point of the loop .

3、 ... and 、 Code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        ListNode* fast = head;
        ListNode* slow = head;

        do{
    
            if(!fast || !fast->next) return nullptr;
            fast = fast->next->next;
            slow = slow->next;
        }while(fast!=slow);

        fast = head;
        while(fast!=slow){
    
           fast = fast->next;
           slow = slow->next;
        }
        return fast;
    }
};