单向循环链表

1.如何判断有头结点的链表是否有环

快（fast）慢（slow）指针：

1.设置快慢指针，同时从头结点的后继节点（第一个有效节点）出发。

2.快指针每次走两步，慢指针每次走一步，当快慢指针相遇时，即说明存在环（利用速度差制造 “有环必相遇” 的条件）

核心原理：若链表有环：当slow进入环后，fast已经在环内绕圈；由于相对速度是 1，fast与slow的距离会每轮缩小 1 步，最终必然相遇（不会 “跳过” 对方）。

• 快慢指针的相对速度 = 1 步 / 轮（fast 每轮比 slow 多走 1 步），无论 slow 进入环时与 fast 的初始距离是n，每轮距离都会减少 1，最终必然缩小到 0（相遇）；
• 若选其他步数（如 fast3 步、slow1 步，相对速度 2），当环长为偶数、初始距离为奇数时，距离会一直是奇数（如 1→-1→1→-1，模环长后永远无法为 0），导致 “有环但永远不相遇”；
• 2 步 + 1 步是唯一能保证 “有环必相遇” 的最小步数组合，也是效率最高的（遍历次数最少）。

易错点补充（豆包）

• 不要 “先移动指针再判断相遇”：若先移动再比较，初始时slow=fast（首元节点）会被跳过，但逻辑仍成立；但先判断再移动会误判初始位置为 “有环”（比如只有头结点 + 1 个节点时，初始 slow=fast = 首元节点，直接返回 1，错误）；
• 头结点的 “空指针检查” 必须优先：工业级代码中，第一步要判断head是否为 NULL，避免后续访问head->next崩溃。

流程图如下：（图片中6和7的位置应该互换，抱歉创作的时候没有仔细看）

核心代码实现

2.如何找到循环链表的入口（进入环的环口）

第一步：先确定环中有多少结点（环的长度是第一次相遇时 fast 比 slow 多走的步数（通常为 1 倍环长）（即在第一次相遇后可以创建变量count=1，记录环中结点的个数）在再次相遇之前，fast 与 slow 每挪动一个单位长度，count 值就加一，这样的同时也意味着count的值可作为快慢指针的依据）

第二步：重新让fast和slow指向头结点，fast比slow先走count步，然后再同时走，此时fast和slow的步长均为1步（为什么这样能够找到环口（豆包补充）

假设：

• 头节点到环入口的距离为L；
• 环入口到相遇点的距离为X；
• 环长为count。

第一次相遇时：

• slow走的总路程：L + X；
• 由前面的推导，slow走的总路程 = 环长 →L + X = count→L = count - X。

当fast先走count步后，fast的位置：count（总步数）=L + X + (count - L - X)（绕环的部分）→ 等价于fast走到 “相遇点”，再往回退X步（即环入口位置）；此时slow从头节点出发，fast从 “count 步位置” 出发，两者同速（步长 1）走L步后：

• slow走到环入口（走了L）；
• fast从count步位置走L步 →count + L = (L + X) + (count - X) + L = L（环内绕圈后），也到达环入口；因此两者会在环入口相遇。

）

第三步；再次相遇的结点即为环的入口

流程图：

蓝色标注的内容即为第二步的内容

核心代码实现（图源b站逊哥）：

这里的循环条件p->next != slow解读为：当p->next == slow时，即p的下一个结点回到相遇点，此时p刚好绕环走了一圈，避免掉再记一次相遇点，造成环的结点计数错误；若为p！= slow会造成循环条件从一开始就不成立，count的数值永远为初始值1，无法正常统计环的长度。