https://leetcode.cn/problems/linked-list-cycle-ii/description/

<aside> 💡

这题需要一定的数学推理，最好拿张纸画个图然后动笔算一算

思路分为两部分——是否有环 + 如何找到环的入口：

• 是否有环：设计快慢指针，快指针每次比慢指针多移动一个节点。如果两指针能相遇就说明有环
• 如何找到环的入口：需要一定的数学推理，见下图 </aside>

<aside> 💡

环的入口距离头节点x个节点，也距快慢指针相遇点z个节点。由于x = (n - 1)(y + z) + z，那么两个节点分别从快慢指针相遇点和头节点开始以相同速度移动，他们的相遇点一定是环的入口！（y+z等于一圈，所以在环内移动了y+z等效于移动0）

</aside>

ListNode* detectCycle(ListNode* head) {
	// 快指针比慢指针移动速度快1，相当于每次移动就靠近慢指针一个节点，如果有环就一定会相遇
	ListNode* fast = head;		// 快指针，一次移动两个节点
	ListNode* slow = head;		// 慢指针，一次移动一个节点

	// 找到快慢指针相遇的节点
	do {
		if (fast && fast->next) {
			fast = fast->next->next;
			slow = slow->next;
		}
		// 有终点说明不存在环
		else {
			return nullptr;
		}
	} while (fast != slow);
	// slow指针重置回头节点，fast指针停留在相遇点
	slow = head;
	// 两指针以同样速度移动，再次相遇时就是环的入口节点（这步需要一定的数学推理）
	while (fast != slow) {
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}