【LeetCode热题100】【链表】环形链表 II

题目链接：142. 环形链表 II - 力扣（LeetCode）

同：【LeetCode热题100】【技巧】寻找重复数-CSDN博客

如果有环，快慢指针一定会在环内相遇，假设从链表头到环入口距离为a，快慢指针相遇处距入口距离为b，那么慢指针走了a+b，而快指针走了2a+2b，记相遇处绕回到入口处距离为c，那么快指针多走了一圈，即c+b，即a=c，此时让一个指针从链表头开始走c步，一个指针同时在相遇处走c步，那么他们会在入口相遇

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        do {
            if (slow == nullptr || slow->next == nullptr || fast == nullptr || fast->next == nullptr)
                return nullptr;
            slow = slow->next;
            fast = fast->next->next;
        } while (fast != slow);
        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};