Question 141 of Li Kou: circular linked list

Power button 141 topic ： Circular list

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 ：true
 explain ： There is a link in the list , Its tail is connected to the second node .

 Input ：head = [1,2], pos = 0
 Output ：true
 explain ： There is a link in the list , Its tail is connected to the first node .

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

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

bool hasCycle(ListNode *head)
{
    
    // establish hash surface 
    unordered_set<ListNode*>sets;

    while(head!=nullptr)
    {
    
        // As long as one already exists, it will jump out of the ring of existence 
        if(sets.count(head))
        {
    
            return true;
        }

        sets.insert(head);
        head=head->next;
    }
    return false;

}

Solution 2 , The idea of using fast and slow pointers

// Solution 2 , Borrow the idea of speed pointer , If there is a ring , Then the two will meet , namely   Move two steps at a time , Move one step at a time 
bool hasCycle(ListNode *head)
{
    
    if(head==nullptr||head->next==nullptr)
    {
    
        return false;
    }

    // Define speed pointer 
    // Set the starting point of both , Because we should try to meet the cycle conditions, the starting points of the two are different , But it doesn't affect the results 
    ListNode *slow=head;
    ListNode *fast=head->next;

    while(slow!=fast)
    {
    
        // When the fast pointer equals nullptr, Or its next node is equal to nullptr, It means that there must be no ring in the linked list 
        // Because the length of the linked list is unpredictable , And the fast pointer moves faster than the slow pointer 
        if(fast==nullptr||fast->next==nullptr)
        {
    
            return false;
        }
        // Set the step size of each movement 
        slow=slow->next;
        fast=fast->next->next;
    }

    return true;
}