// 假设有环, 从 head 到环入口有 a 个节点, 环大小为 b 个节点, c 表示从环入口到停下来地方的结点数
// slow 与 quick 相遇时有等式: 2 * (a + x * b + c) = a + y * b + c
// 即 2 * a + 2 * x * b + 2 * c = a + y * b + c
// a = -c + (y - 2 * x) * b
// 显然 a >= 0. 所以换句话说就是, a = 若干圈 * b - c, 也就说 (若干圈 - 1) * b + (b - c)
// 所以, 从起点开始, 和停下来的地方继续同步走, 再次相遇的地方就是 环入口

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr || head -> next == nullptr) return nullptr;
        ListNode *slow = head -> next, *quick = head -> next;
        while(quick && slow != quick) {
            slow = slow -> next;
            quick = quick -> next;
            if(quick) quick = quick -> next;
        }
        if(quick == nullptr) return nullptr;
        // 有环, 接下来 quick 与 slow 一样, 一次走一步, 当 quick 再次等
        // 于 slow, 则此点为入口
        slow = head;
        while(slow != quick) {
            slow = slow -> next;
            quick = quick -> next;
        }
        return slow;
    }
};