链表带环检测与入口定位：快慢指针法原理及实现
链表带环问题是数据结构中的经典考点，核心在于通过快慢指针法判断环的存在并定位入口点。本文从两道典型真题出发，拆解快慢指针的相遇逻辑与数学推导，结合代码实现与严谨证明，清晰呈现带环链表的解题思路。
一、带环链表检测
1.1 题目描述
给定一个链表，判断其中是否包含环。如果链表中存在某个节点可以通过连续追踪 next 指针再次访问到，则说明存在环。
1.2 核心思路
核心思想： 快慢指针 —— 相遇即为链表带环。
创建两个指针 slow 和 fast，初始均指向头结点 head。遍历时 slow 每次走一步，fast 每次走两步。这将产生两种情况：
- 链表不带环：
fast一定可以遍历到NULL。 - 链表带环：
fast一定比slow先进入循环。在环内不断追赶，当slow也进入循环时，由于速度差，两者必定会在环内相遇。
1.3 代码实现
/** Definition for singly-linked list. */
struct ListNode {
int val;
struct ListNode *next;
};
typedef struct ListNode* ListNode;
bool hasCycle(struct ListNode *head) {
ListNode slow = head;
ListNode fast = head;
// 只要 fast 和 fast->next 不为空即可继续
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
// 链表相遇
if (fast == slow) return true;
}
// 能跳出循环 --- 不带环
return false;
}
1.4 数学证明
1.4.1 为什么带环 slow 与 fast 必定能相遇？
假设 slow 进环时与 fast 的差距为 $N$。接下来就是追击问题，slow 每次走一步，fast 每次走两步。每走完一次，slow 的距离就会变成：$N - 1, N - 2, \[dots], 2, 1, 0$，故必定会相遇。
