环形链表是链表中的一类特殊问题，它和链表反转一样，有着相对恒定的解题思路和适当的变体。如果你对它的特性和解法没有预先的了解和把握，那么前期的推导可能会花去你大量的时间。反过来看，只要我们能够掌握其核心思路，那么不管它怎么变化，大家都能在瞬间找到解题的“抓手”、进而给出正确的解答。
# 环形链表基本问题——如何判断链表是否成环？
30 秒速记
- 能改结点：沿路给结点打
flag，再碰到打过标记的就是有环 - 不能改结点：
Floyd快慢指针，slow一步、fast两步，相遇就有环 fast或fast.next先到null就是无环- 比的是结点引用
slow === fast，不是val Floyd：O(n)时间、O(1)空间；Set记引用更直观但O(n)空间
判环最直观的是边走边给结点做标记，再碰到标记过的就说明绕回来了；但这会改输入，所以我一般用 Floyd 快慢指针。 想象操场跑圈，跑得快的人迟早会从后面追上跑得慢的。slow 每次走一步，fast 每次走两步，有环的话进了环之后 fast 每轮追近一步，一定会撞上；没环的话 fast 会先走到 null。比较时一定比引用，两个结点值一样不代表是同一个结点。
let slow = head, fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) return true
}
return false
回答参考：“我先确认不能修改节点。然后用 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两个结点 val 都是 7，判环函数返回了 true，错在哪？
比的是值不是引用。成环是指沿着 next 又回到了「同一个对象」，值相同的两个独立结点不能说明任何事。要写 slow === fast。
追问 2给结点写 flag 判环，有什么问题？
改了输入。结点要是被冻结了写不进去，共享的结点还会把标记留给下一次调用，第二次判环直接误报。不想改输入就用 Floyd，或者 Set 存引用。
追问 3单结点链表跑判环报 Cannot read properties of null，代码里少了什么？
每次移动前没检查 fast.next。单结点时 fast.next 是 null，再取 .next 就炸了。条件写 while (fast && fast.next)。
追问 4为什么快指针一定能追上，不会刚好跳过去？
进了环之后看相对速度：fast 每轮比 slow 多走一步，两者距离每轮减一，减到 0 就是相遇，不存在跳过。走三步的话一轮缩两格，才可能跨过去。
追问 5链表来自只读 SDK、长度不确定，Set 和 Floyd 选哪个？
Floyd。不改结点，内存是常数级。Set 要存下所有结点引用，链表很长时内存不可控，适合想顺便记录访问路径、做诊断的场景。
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 秒速记
- 打
flag法：第一个被发现「已经有标记」的结点就是入口 Floyd两阶段：第一阶段相遇只说明有环，相遇点不一定是入口- 第二阶段：一个指针回
head，两个都每次走一步，再相遇的地方就是入口 - 推导：设头到入口
a，入口到相遇点b，环长c，有a = k·c - b - 无环直接返回
null，别拿着空的相遇点进第二阶段
找环的入口，先用快慢指针找到相遇点，然后把一个指针放回头结点，两个指针都改成一次走一步，再次相遇的地方就是入口。 原因是：相遇时 fast 走的路程是 slow 的两倍，2(a + b) = a + b + k·c，化简得 a = k·c - b。也就是说，从头走 a 步到入口，和从相遇点继续走 a 步，都会落在入口上。第一阶段 fast 走到 null 就直接返回 null。
// 第二阶段
let finder = head
while (finder !== slow) {
finder = finder.next
slow = slow.next
}
return finder // 入口结点
回答参考：“先用 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;
};
面试官追问
追问 11→2→3→4→5→3 里，第一次相遇就直接返回相遇点，对吗？
不对。这里入口是 3，快慢指针走三轮后在 4 相遇。相遇点只能证明有环，要找入口还得走第二阶段。
追问 2第二阶段写成一个走一步、另一个走两步，会怎样？
推导就不成立了，a = k·c - b 是在两人同速的前提下才抵得上。速度不同的话不保证在入口碰面，甚至一直在环里错开。
追问 3用 Set 从头走，第一个重复的结点就是入口，这样行不行？
行，而且很直观，第一个被见过两次的结点一定是入口。代价是 O(n) 额外空间。只读、追求常数空间时用 Floyd。
追问 4找到入口后要把环断开，改哪个结点？
改环里的最后一个结点，也就是 node.next === entry 的那个，把它的 next 设成 null
