Lecture 1: the entry node of the link in the linked list

subject ： The entry node of a link in a list
Given a linked list , If it contains rings , Then the inlet node of the output ring .

If it does not contain a ring , The output null.

Data range
node val Value range [1,1000].
Chain length [0,500].

Examples

Given the linked list shown above ：
[1, 2, 3, 4, 5, 6]
2
Be careful , there 2 Indicates that the number is 2 The node of , Node number from 0 Start . So the number is 2 The node of is val be equal to 3 The node of .

Then the inlet node of the output ring 3.

title ：
Method 1 ： Hashtable
We can use unordered_set, To save the node pointer , If the same pointer is found （set The size of the remains the same ）, It means the entry node

Method 2 ： Speed pointer
principle ： Two steps at a time , Slow pointer one step at a time , If there is a ring, it must meet
Pictured , Suppose the slow pointer starts from a Go to the b Finally, I met the fast pointer in c, If the slow pointer returns to b spot , Then the fast pointer will return to d spot （ Because I will walk more y Step ）
Then we can find that when the slow pointer goes b spot , Then the pointer will go to d spot （ Because of the fallback ）, that x+y It will be an integral multiple of the circle （ In fact, the fast pointer may have gone through many circles , But it doesn't affect , It is equivalent to the remainder operation ）
Finally, we move the slow pointer to the starting point , The two pointers take the same number of steps , Will meet at the entrance （ Because the fast pointer has gone y Step , To walk again x Step will definitely be b spot , And slow the pointer x Step will also be in b spot ）

Number of executions ：x+y+2x+2y+2x=5x+3y（ because x+y Less than the total length , So time complexity 0（n））

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
    
        if(!head)return NULL;
        set<ListNode *> s;
        while(head->next)
        {
    
            int size=s.size();
            s.insert(head);
            if(size==s.size())return head;
            head=head->next;
        }
        return NULL;
    }
};