快慢指针法

本质在于“相对速度”，用速度差来刻画路径长度。

比如——

• 如果路径中有环，快慢指针一定可以相遇；假设速度差是1，快慢指针相遇之后，慢指针继续走，另外放一个慢指针从头走，则再次相遇时必然就是环的入口。

• 如果路径无环，快指针速度是慢指针的两倍，则快指针到达终点时慢指针刚好到中点。

• 快指针先走 N 步，然后快慢指针一起走（速度相同，都是 1 步）。当快指针走到终点时，慢指针刚好停在倒数第 N 个节点的前一个位置。

环形链表

找到环形链表里的环有两种思路。

一种非常直接，用一个 unordered_set 存一下所有的 Node*，然后开始遍历链表。如果遇到重复就return。

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

            visited.insert(cur);
            cur = cur->next;
        }

        return nullptr;
    }
};

//对应LC142

另一种则是快慢指针法，在内存上做了极致的优化。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;        // 慢指针走1步
            fast = fast->next->next;  // 快指针走2步
            
            // 找到第一个相遇点
            if (slow == fast) {
                // 一个指针放回头节点，另一个留在相遇点
                ListNode* ptr1 = head; // 从头走
                ListNode* ptr2 = slow; // 从相遇点走
                while (ptr1 != ptr2) {
                    ptr1 = ptr1->next;
                    ptr2 = ptr2->next;
                }
                // 再次相遇的地方，就是环入口
                return ptr1;
            }
        }
        return nullptr; // 没环
    }
};