// 假设有环, 从 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;
}
};
leetcode 环形链表II 中等