Question 142 of Li Kou: circular linked list 2

Power button 142 topic ： Circular list 2

Title Description

Give you a list of the head node head , Judge whether there are links in the list .

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 ）. Be careful ：pos Not passed as an argument . Just to identify the actual situation of the linked list .

If there are rings in the list , Then return to true . otherwise , return false .

I/o sample

 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 .

 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 .

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

Solution 1 ： Use hash Table is stored , The space complexity is O(n)

// Use hash Table to establish the traversal relationship between nodes 
ListNode *detectCycle(ListNode *head)
{
    
    unordered_set<ListNode *>sets;

    while(head!=nullptr)
    {
    
        if(sets.count(head))
        {
    
            return head;
        }
        else{
    
            sets.insert(head);
            head=head->next;
        }
    }

    return nullptr;
}

Solution 2 , The thought space complexity of using the fast and slow pointer is O(n)

// Use the idea of fast and slow pointer to complete 
// The node passed by the slow pointer :  Outside the ring  a , In loop displacement b,  Residual displacement in the ring c,  Total number of moves n  Total mobile nodes  a+n(b+c)+b
// Fast pointer to the node ：  The speed of the fast pointer is twice that of the slow pointer  , But the number of knots is the same  (a+b)*2=(a+n(b+c)+b) 

//a+b=n(b+c) a=(n-1)b+nc a=(n-1)(b+c) +c
// With n=1 Value 
// a=c
ListNode *detectCycle(ListNode *head)
{
    
    ListNode *fast=head;
    ListNode *slow=head;

    while(fast!=nullptr &&fast->next!=nullptr)
    {
    
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
    
            ListNode *index1=fast;
            ListNode *index2=head;

            //a=c
            //n=1, Only over 1 circle 
            while(index1!=index2)
            {
    
                index1=index1->next;
                index2=index2->next;
            }
            // Return to the intersection 
            return index2;
        }
    }
    return nullptr;
}