引言
环形链表问题是数据结构与算法中的经典问题，在面试中出现频率极高。这类问题不仅考察对链表结构的理解，更考验解决问题的思维能力和数学分析能力。本文将详细分析环形链表的判断方法以及环入口节点的定位算法。
环形链表判断
问题描述
给定一个链表的头节点 head，判断链表中是否存在环。
解决方案：快慢指针法
快慢指针法是解决环形链表问题的经典方法，其核心思想是使用两个指针以不同速度遍历链表。
bool hasCycle(struct ListNode* head) {
struct ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
// 一定要先让快慢指针走，再判断，因为一开始快慢指针都是 head
if (slow == fast) return true;
}
return false;
}
原理分析
为什么快慢指针一定能相遇？
假设慢指针进入环时，快指针与慢指针之间的距离为 N。由于快指针每次比慢指针多走一步，它们之间的距离会逐次减少：N, N-1, N-2, …, 2, 1, 0。因此最终一定会相遇。
步长选择的数学分析
为什么选择一步和两步？
当快指针每次走三步、四步或更多时，情况会变得更加复杂。以三步为例：
- 每次移动后，快慢指针之间的距离减少 2
- 当 N 为偶数时，可以追上
- 当 N 为奇数时，会错过，距离变为 C-1（C 为环长）
假设 slow 进环时，fast 跟 slow 的距离是 N。
fast 追击 slow 时 距离变化为 N N-1 N-2 ……2 1 0 所以能追上
