环形链表 II 图解题解
快慢指针能判断链表有没有环，但环从哪里开始——这才是真正的难题。
操场上两个人跑圈，跑得快的那个总会追上慢的——相遇证明有环。找到相遇点之后有个数学结论：让一个人回到起跑线，两人再以同样速度走，再次相遇的地方就是圈的入口。不用记路，不用额外做标记，两次相遇就把入口精确锁定，全程 O(1) 空间。
这道题到底在问什么
- head, pos
- [3,2,0,-4]，尾部连回下标 1
- 输出
- 值为 2 的节点（入环口）
最优解：一步一步想明白
- 3边走边把节点存进集合，第一个重复出现的节点就是入口。直观，但要 O(n) 空间。
- 4Floyd 判环分两段：第一段快慢相遇证明有环，第二段一个指针回到头，两指针同速走，再相遇就是入口。
- 5slow = fast = head（值 3）先让慢指针和快指针都站在头节点 3。注意尾节点 -4 沿回绕箭头连回 2。
- 6slow: 3 → 2慢指针每轮只走一步，从 3 走到 2。
- 7fast: 3 → 2 → 0快指针一轮走两跳，把它拆开看：先到 2，再到 0。这一轮结束 slow 在 2、fast 在 0，还没相遇。
- 8slow: 2 → 0 ；fast: 0 → -4 → 2第二轮 slow 走到 0；fast 从 0 到 -4，再沿回绕箭头回到 2。这轮 slow 在 0、fast 在 2，仍没相遇。
- 9slow = fast = -4（相遇点）第三轮 slow 到 -4；fast 从 2 到 0、再到 -4。两个指针踩在同一个节点 -4 上，相遇了，证明有环。但注意：相遇点 -4 并不是入口，入口是 2。
- 10p = head（3）；slow 留在 -4进入第二阶段：新指针 p 回到头节点 3，slow 留在相遇点 -4。接下来两个指针每次都只走一步，速度一样。
- 11p: 3 → 2 ；slow: -4 → 2两指针各走一步：p 从 3 到 2；slow 从 -4 沿回绕箭头回到 2。它们在节点 2 第二次相遇——这个节点就是环的入口，直接返回它。
- 12头到入口 = 相遇点到入口（同一段距离）这才是这题的关键帧。设头到入口的距离是 a，入口到相遇点是 b，环长是 c。相遇时快指针走的路是慢指针的两倍，推一下能得到 a 恰好等于「从相遇点再绕回入口」的距离。所以让一个指针从头走 a 步、另一个从相遇点走同样多步，它们必然同时落在入口。这就是为什么第二次相遇点就是答案。
- 15第一段答「有没有环」，第二段答「环口在哪」。
- 18相遇在 -4，入口却是 2看清楚：两指针相遇在 -4，但环的入口是 2。如果在这里直接返回 slow，就返回错了节点。必须进第二阶段再走一遍。
- 23这题学完别乱跳，去 链表专题 连刷同类；卡在「为什么 a=kc−b」时用 AI 答疑追问推导，比背结论更稳。
⚠️ 容易写错的地方
✗ 错：把相遇点 -4 当成入口返回
✓ 对：相遇后再让一个指针从 head 同步走
相遇点在环内，未必是入口，只有第二段再相遇才是入口。
✗ 错：循环里不判 fast.next
✓ 对：while 同时判 fast 和 fast.next 非空
fast 要走两步，无环时会走到 null 触发空指针。
✗ 错：比较节点值是否相等
✓ 对：比较是不是同一个节点对象
不同节点可能有相同值，要比引用而不是比 val。
完整代码（Python / C++ / Java）
Python
class Solution:
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p = head
while p is not slow:
p = p.next
slow = slow.next
return p
return NoneC++
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *p = head;
while (p != slow) {
p = p->next;
slow = slow->next;
}
return p;
}
}
return nullptr;
}
};Java
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
}套路模板 · 挖空骨架
# 阶段一：快慢指针找相遇点
slow = fast = head
while ____ and ____: # fast 和 fast.next 都不为空
slow = slow.next # 慢走一步
fast = fast.next.next # 快走两步
if slow is fast: # 相遇 → 进阶段二
p = head
while ____: # p 与 slow 还没相遇
p = p.next # 两指针同速各走一步
slow = slow.next
return p # 再相遇点 = 入口
return None # fast 到 null = 无环// 阶段一：快慢指针找相遇点
ListNode *slow = head, *fast = head;
while (____ && ____) { // fast && fast->next
slow = slow->next; // 慢走一步
fast = fast->next->next; // 快走两步
if (slow == fast) { // 相遇 → 阶段二
ListNode *p = head;
while (____) { // p != slow
p = p->next; // 同速各走一步
slow = slow->next;
}
return p; // 再相遇点 = 入口
}
}
return nullptr; // 无环// 阶段一：快慢指针找相遇点
ListNode slow = head, fast = head;
while (____ != null && ____ != null) { // fast、fast.next 非空
slow = slow.next; // 慢走一步
fast = fast.next.next; // 快走两步
if (slow == fast) { // 相遇 → 阶段二
ListNode p = head;
while (____) { // p != slow
p = p.next; // 同速各走一步
slow = slow.next;
}
return p; // 再相遇点 = 入口
}
}
return null; // 无环复杂度
时间复杂度
O(n)
第一段最多走 n 步相遇，第二段最多再走 n 步到入口
空间复杂度
O(1)
只用 slow / fast / p 三个指针，不开哈希集合
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 环形链表 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么第二阶段再相遇就是入口？+
设头到入口 a、入口到相遇点 b、环长 c。快是慢两倍：2(a+b)=a+b+kc，得 a=kc−b，即「从头走 a」与「从相遇点走 a」会同时到入口。
和 LC141 判环有什么区别？+
LC141 只做第一阶段，相遇就返回 true；LC142 多一个第二阶段，把相遇点转换成环入口。
哈希法和快慢指针怎么选？+
哈希法第一个重复节点就是入口，O(n) 空间更直观；快慢指针 O(1) 空间，是面试更想看的答案。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。