姿势特别的链表——环形链表专题|算法篇
环形链表是链表中的一类特殊问题，它和链表反转一样，有着相对恒定的解题思路和适当的变体。如果你对它的特性和解法没有预先的了解和把握，那么前期的推导可能会花去你大量的时间。反过来看，只要我们能够掌握其核心思路，那么不管它怎么变化，大家都能在瞬间找到解题的“抓手”、进而给出正确的解答。
# 环形链表基本问题——如何判断链表是否成环？
30 秒速记
- 不修改链表时首选 Floyd 快慢指针：
slow每次一步，fast每次两步。 - 有环时快指针会在环内追上慢指针；无环时
fast或fast.next先到null。 - 时间
O(n)、额外空间O(1)；Set法更直观但空间为O(n)。 - 循环条件先保护
fast && fast.next，比较的是节点引用而不是节点值。
不修改链表的情况下，我一般用 Floyd 快慢指针判断是否有环。 slow 每轮走一步，fast 每轮走两步；进入有限长度的环后，快指针会不断缩短与慢指针的相对距离，最终相遇。若 fast 或 fast.next 先变成 null，则说明没有环；实现时比较节点引用而不是节点值，时间为 O(n)、额外空间为 O(1)。
回答参考：“我先确认不能修改节点。然后用 Floyd 判环：快慢指针进入有限长度的环后，相对位置每轮前进一格，所以必然相遇；若快指针抵达 null，则无环。”
真题描述：给定一个链表，判断链表中是否有环。
示例 1：
输入：[3,2,0,4]（链表结构如下图） 输出：true
解释：链表中存在一个环
思路解读
其实链表成环的特征非常明显，大家可以结合一个现实中的例子来理解：
假如现实中有一个长跑爱好者李雷，这货很狂，他立了一个 flag，说要徒步环游世界：
地球的周长围出来的这个圆，它就是一个“环”。李雷现在就想围着这个环跑上一圈，说他狂，他也没那么狂——他觉得自己最多跑一圈，为了防止自己跑过界，他决定在出发的地方立一个 flag：
这样，不管李雷走完这个环用了多少年，世事如何变迁，只要他的 flag 还没有倒，那么李雷就一定能回到自己梦开始的地方：）。
换个角度看：只要李雷在闷头前进的过程中，发现了 flag 的存在，那么就意味着，李雷确实走了一个环。毕竟若这是一条线，他将永远无法回到起点。
回到链表的世界里，也是一个道理。一个环形链表的基本修养，是能够让遍历它的游标回到原点
从 flag 出发，只要我能够再回到 flag 处，那么就意味着，我正在遍历一个环形链表。
我们按照这个思路来做题：
编码实现
/**
* @param {ListNode} head
* @return {boolean}
*/
// 入参是头结点
const hasCycle = function(head) {
// 只要结点存在，那么就继续遍历
while(head){
// 如果 flag 已经立过了，那么说明环存在
if(head.flag){
return true;
}else{
// 如果 flag 没立过，就立一个 flag 再往
下走
head.flag = true;
head = head.next;
}
}
return false;
};
面试官追问
追问 1调试页里两个不同节点的 value 都是 7，判环函数因此返回 true；为什么比较节点值会产生误判？
成环意味着沿 next 再次到达同一个节点对象，而不是再次看到相同的业务值。判定时必须比较节点引用；两个独立节点即使 value、时间戳等字段完全相同，也不能证明链表存在环。
追问 2共享缓存中的链表节点被冻结且会被多个请求复用，开发者提出写入 flag 判环；你会接受吗？
不应直接写入 flag，冻结节点可能让赋值失败，共享结构还会把一次遍历留下的标记带给后续请求。应使用 Floyd 快慢指针保持 O(1) 额外空间；若允许额外内存，也可用按引用存储的 Set。
追问 3数据导入链表可能包含上百万节点，产品要求不修改输入且额外空间保持常数级，你会如何判断是否成环？
应让 slow 每轮走一步、fast 每轮走两步，并在移动前检查 fast 和 fast.next。若二者引用相同则存在环，若快指针到达 null 则无环；该方案时间为 O(n)，且不会随节点数增加额外集合空间。
追问 4线上单节点链表执行判环后偶发 Cannot read properties of null，代码直接写了 fast = fast.next.next；你会检查什么？
应先确认每轮移动前是否同时判断 fast 与 fast.next，任一为空都应立即返回无环。单节点无环、空链表和尾部只剩一个节点都会触发该边界；仅在移动之后检查已经来不及阻止空引用访问。
追问 5评审中一方选择 Set，另一方选择 Floyd；链表来自只读 SDK 且长度不可预估，你会支持哪一个？
更适合选择 Floyd，因为它不修改 SDK 节点，也只占用常数额外空间，长度不可预估时内存风险更低。Set 的实现更直观并能保留访问痕迹，但需要 O(n) 空间，只有诊断需求高于内存约束时才更合适。
function hasCycle(head) {
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) return true
}
return false
}
# 环形链表衍生问题——定位环的起点
30 秒速记
- 第一阶段让快慢指针相遇，只证明“有环”。
- 第二阶段把一个指针放回头节点，两者都每次一步；再次相遇处就是环入口。
- 设头到入口为
a、入口到首次相遇为b、环长为c，可推出头到入口与相遇点到入口的剩余距离同余。 - 无环必须返回
null，不能在第一阶段退出后继续访问相遇点。
我会先用 Floyd 快慢指针找到环内相遇点，再让一个指针回到头节点，与另一个指针同步前进，再次相遇的位置就是环入口。 本质上，快指针路程是慢指针的两倍，可以推出头节点到入口的距离，与相遇点继续绕到入口的距离对环长同余。若第一阶段发现 fast 或 fast.next 为 null，必须直接返回 null，不能继续访问所谓的相遇点。
回答参考：“先用 Floyd 找相遇点。由快指针路程是慢指针两倍可推出，头到入口的距离等于相遇点继续绕到入口的距离模环长，因此两个指针同步走会在入口相遇。”
真题描述：给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。
示例 1：
输入：head = [3,2,0,-4]（如下图） 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个结点。
示例 2：
- 输入：head = [1,2]（如下图）
- 输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个结点。 链表成环2
示例 3：
- 输入：head = [1]（如下图）
- 输出：no cycle
解释：链表中没有环。
思路解读
这道题在上道题的基础上，仅仅增加了一个“返回链表的成环起点”，其难度定义就从 easy 上升到了 medium。不过对于掌握了关键解题思路的各位来说，这道题仍然是 easy——因为如果一个结点是环形链表成环的起点，那么它一定是第一个被发现 flag 标志已存在的结点：
这一点不难理解，我们试想如果从头开始遍历一个链表，假如途中进入了一个环，那么首先被打上 flag 标签的其实就是环的起点。待我们遍历完这个环时，即便环上所有的结点都已经被立了 flag，但起点处的 flag 一定最先被我们定位到。因此，我们只需要在第一次发现 flag 已存在时，将对应的结点返回即可：
编码实现
/**
* @param {ListNode} head
* @return {ListNode}
*/
const detectCycle = function(head) {
while(head){
if(head.flag){
return head;
}else{
head.flag = true;
head = head.next;
}
}
return null;
};
面试官追问
追问 1链表 A→B→C→D→C 中，代码在快慢指针首次相遇时直接返回相遇节点；页面却要求返回 C，错在哪里？
首次相遇只能证明存在环，相遇位置并不保证就是入口 C。应把一个指针重置到 head，另一个留在相遇点，再让二者每次各走一步；下一次引用相同的位置才是入环的第一个节点。
追问 2日志采集链表禁止增加字段，接口还要求无环时返回 null；你会怎样实现入口定位并处理空链表？
应先用 Floyd 完成判环，移动前检查 fast 和 fast.next，到达尾部就返回 null。相遇后再启动从 head 出发的 finder 与慢指针同步前进，最终返回共同节点，全程不需要修改输入。
追问 3安全审计要求在找到入口后断开环，但该链表还被另一个读线程共享；你会直接修改入口节点吗？
不能直接修改入口，因为要断环的是环内满足 node.next === entry 的前驱节点，将其 next 设为 null。共享读线程可能同时观察到结构突变，必须先确认所有权或加同步措施；若无修改授权，只应返回入口而不改链表。
追问 4线上实现对部分长链表一直循环，监控显示已找到首次相遇点，但第二阶段一个指针走一步、另一个走两步；你会如何修复？
第二阶段必须让从 head 出发的指针和相遇点指针都每次走一步。入口推导依赖两段剩余距离在相同速度下抵消，改变速度后不再保证在入口相遇，甚至可能只在环内周期性错过。
追问 5内存充足的后台任务想用 Set 直接返回首个重复节点，核心库坚持 Floyd；两种方案如何取舍？
从头遍历并按引用加入 Set 时，首次重复的节点确实是入口，实现直观但需要 O(n) 额外空间。Floyd 只占常数空间且不修改节点，更适合通用核心库；若任务更重视可观测性并接受内存增长，Set 也成立。
追问 6定位入口后，排障人员还想知道环长以评估损坏范围；你会复用哪个状态继续计算？
可从首次相遇点出发，固定一个指针，让另一个每次走一步，直到再次回到该点，累计步数就是环长。该过程仍为 O(1) 额外空间，但必须在已确认有环后执行，否则沿无环链表计数会遇到 null。
# 快慢指针的思路
30 秒速记
- 慢指针每轮一步、快指针每轮两步；无环时快指针先到
null，有环时二者最终必在环内相遇 - 循环条件要同时检查
fast和fast.next，否则读取fast.next.next会越界 - 比较的是结点引用而不是结点值，相同值不代表走到了同一个位置
快慢指针的核心是让 slow 每轮走一步、fast 每轮走两步，用二者是否相遇来判断链表有没有环。 有环时，两者进入环后会因速度差最终相遇；无环时，快指针会更早走到链表末尾。循环中要检查 fast 和 fast.next，否则读取 fast.next.next 可能出错；同时必须比较节点引用，相同的节点值并不代表处在同一位置。
