/**
 * 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* temp = head;
        while(temp != nullptr && temp->val <100001){
            temp->val += 1000000;
            temp = temp->next;
        }
        if(temp == nullptr){return temp;}//Considering that there are no links in the linked list
        ListNode* ans = temp;
        temp = head;
        while(temp->val > 100001){
            temp->val -= 1000000;
            temp = temp->next;
        }
        return ans;
    }
};

This problem first still uses a trick to change the value as a marker, then traverse, and finally change the value back.

At the same time, it should be noted that one million is added here, because a negative value may be taken here. Therefore, if only one hundred thousand one is added, the result may not be greater than one hundred thousand one, so the addition and non addition are inseparable, so one million is added directly to distinguish.

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

Author: LeetCode-Solution
 Link: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

The general idea of the standard answer is the same as mine. The difference is that I mark it by changing the value, and the answer is to load the elements through the hash table, which is equivalent to a mark (whether it has been accessed or not).

Double finger needle method: (for example, this method is commonly used to find the K-th node from the tail in the linked list, find the ring entrance, find the common tail entrance, etc.)

Author: jyd
Link: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

Idea:
(1) Judge whether there is a ring;
(2) When meeting for the first time, the path f traveled by fast is n more than the path s traveled by slow, that is, f=s+nb(b is the circumference of the ring);
(3) At the same time, starting from head, it is obvious that f = 2s, so s = nb, that is, the distance traveled by the slow pointer at the first encounter is an integral multiple of the circumference of the ring;
(4) At this time, the two pointers start from the first meeting point and head at the same speed. When they both pass through a, they are both at the ring entrance to complete the meeting.

/**
 * 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* fast = head;
        ListNode* slow = head;
        while(fast != slow && fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        if(fast == nullptr || fast->next == nullptr){return fast;}
        fast = head;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

First of all, there is an error demonstration above. The wrong point lies in the fast! = slow in while. Because the initialization is equal, the loop has not been included for such a whole time. The solution is to put the condition judgment inside the loop.

/**
 * 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* fast = head;
        ListNode* slow = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){break;}
        }
        if(fast == nullptr || fast->next == nullptr){return nullptr;}
        fast = head;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

The correction result is as above. At the same time, another change is that for the case of acyclic, nullptr is returned at last, and it also shows that the null pointer can be returned as any type of pointer.