Force buckle 141 Circular linked list

141. Circular list

Given a linked list , 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 , We use integers 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 .

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

Advanced ：

You can use O(1)（ namely , Constant ） Does memory solve this problem ？

Example 1：
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 .

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

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

Tips ：
The number range of nodes in the linked list is [0, 104]
-105 <= Node.val <= 105
pos by -1 Or one of the lists Valid index .

Solution 1 ： Speed pointer

Define two pointers When the fast pointer catches up with the slow pointer, it means that the linked list has a ring

class Solution {
    
public:
    bool hasCycle(ListNode *head) {
    
        if(head == NULL || head->next == NULL)
        return false;
        ListNode *low = head;
        ListNode *fast = head->next;
        // Use while When you cycle, you should put low and fast Set to different  do while  You don't have to 
        while(low != fast)
        {
    
            if(fast == NULL || fast->next == NULL)
                return false;
            low = low->next;
            fast = fast->next->next;
        }
        return true;
    }
};

Time complexity O(N)
Spatial complexity O(1)

Solution 2 ： Hashtable

We traverse each node of the linked list and put it into the hash table Compare nodes , If this node is stored, it is proved that there is a ring , If it traverses to the end, it means there is no ring

class Solution {
    
public:
    bool hasCycle(ListNode *head) {
    
        unordered_set<ListNode *>seen;
        while(head)
        {
    
            if(seen.count(head))
                return true;
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};

Time complexity O(N)
Spatial complexity O(N)