1. The subject

2. Answer

2.1 method 1

The slow pointer moves forward one step at a time, and the fast pointer moves forward two steps at a time. If the list has a ring, the fast and slow Pointers must meet.

When the fast and slow Pointers meet, we make the slow pointer point to the head node, and keep the fast pointer unchanged. Then each time the fast and slow Pointers move forward. When the two Pointers meet again, the node they point to is the entry point.

The loop of the linked list is expanded backward, as shown in the figure above. Assuming that the slow pointer passes through A node, namely s node in the figure, when it meets for the first time, it can be known that the fast pointer points to the same node, namely F node in the figure.

Then, it is assumed that the slow pointer has b nodes from the list head to the entry point, and the fast pointer has C nodes from the fast and slow Pointers to the entry point. In the first encounter, the fast pointer passed through a+ C +a-b nodes, which should be twice as many as the slow pointer, i.e. a+ C +a-b = 2a, so b=c.

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; * /
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        
        if (fast && fast->next)
        {
            slow = head;
            while(slow ! = fast) { slow = slow->next; fast = fast->next; }return slow;
        }
        
        return NULL; }};Copy the code
2.2 method 2

Using unordered_map as the hash table function, each time the linked list node pointer is stored in the map as the key value. If the current node pointer is detected in the map, it means that the current node pointer is the first node in the loop of the linked list.

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
           
        unordered_map<ListNode *, char> nodemap;
        ListNode *temp = head;
        
        while (temp)
        {
            // The current node already exists in map, which is the first node in the loop of the list
            if (nodemap.count(temp) == 1) return temp;
            nodemap[temp] = '0';
            temp = temp->next;
        }
        return NULL; }};Copy the code

For more highlights, watch seniusen!