describe

Judge whether there is a ring in a given linked list . If yes, otherwise return true, Otherwise return to false.

Data range ： Chain length  0≤n≤10000, The value of any node in the linked list satisfies ∣val∣<=100000

requirement ： Spatial complexity  O(1), Time complexity  O(n).

For example, the input {3,2,0,-4} when , The corresponding linked list structure is shown in the figure below ：

  It can be seen that the entry node of the ring is the... From the beginning node 1 Nodes （ notes ： The first node is 0 Nodes ）, So the output true.

The initial definition of the structure is as follows ：

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

Solution 1 Hashtable

1.set Hashtable

class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        set<ListNode*> s;
        while(head!=NULL)
        {
            if(s.find(head)!=s.end())
                return true;
            else
                s.insert(head);
            head=head->next;        
        } 
        return false;
    }
};

2.map Hashtable

class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        map<ListNode*,bool> m;
        while(head!=NULL)
        {
            if(m.find(head)!=m.end())
                return true;
            else
                m[head]=true;// Add key value 
            head=head->next;        
        } 
        return false;
    }
};

The above two methods are essentially the same . All use hash table to judge whether there is a ring in the linked list .

Solution 2 Fast slow double pointer

      Using two Pointers ,fast and slow, Their starting position is the head of the linked list , And then ,slow The pointer moves back one position at a time , and fast Move back two positions at a time , If there are rings in the list , Then these two pointers will eventually meet again .

class Solution
{ 
public:
    bool hasCycle(ListNode* head)
    {
        ListNode *slow = head, *fast = head;
        while ( fast && fast->next) 
        {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast)
                return true;
        }
        
            return false;
    }
};

Solution 3 Soul solution ..（ Not recommended ）

The title says n The range is 0 To 10000, So if the number of cycles is greater than 10000 Does it mean there must be a ring , On the contrary, if the cycle ends after a certain number of times, it means that it must be acyclic ...

class Solution {
public:
    bool hasCycle(ListNode *head) {
        int sum=0;// The title says n The range is 0 To 10000, So if the number of cycles is greater than 10000 Does it mean there must be a ring , On the contrary, if the cycle ends after a certain number of times, it means that it must be acyclic 
        while(head)
        {
            head=head->next;
            sum++;
            if(sum>10000)
                return true;
        }
        return false;
    }
};