#142
中等
中频
双指针环形链表 II
这是一道围绕链表展开的高频练习。建议先掌握「双指针」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
链表
题目分析
给你一条链表，要求判断是否有环；如果有环，还要返回环开始的那个节点。
如果没有环，就返回 null。
一句话概括：
先让快慢指针在环里相遇，再用第二阶段定位环的入口。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：先用快慢指针在环内相遇，再让一个指针回到头部，两者同步前进后再次相遇点就是入环点。
推荐代码
推荐解法：双指针
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 先用快慢指针在环内相遇，再让一个指针回到头部，两者同步前进后再次相遇点就是入环点。
class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
// 初始化快慢指针
ListNode slow = head;
ListNode fast = head;
// 检查是否存在环
boolean hasCycle = false;
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针每次走一步
fast = fast.next.next; // 快指针每次走两步
if (slow == fast) {
hasCycle = true;
break;
}
}
// 如果没有环，返回null
if (!hasCycle) {
return null;
}
// 重置慢指针到链表头部
slow = head;
// 快慢指针同时前进，每次走一步，直到相遇
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// 相遇点即为环的入口
return slow;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会沿用 Floyd 判环，但要分成“先相遇，再找入口”两步来讲。
核心过程
- 第一步先用快慢指针判断是否有环，并让它们在环内相遇。
- 如果无环直接返回 null。
- 相遇后让一个指针回到头节点，另一个留在相遇点。
- 两者同步一步一步前进，再次相遇的位置就是入环点。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题最容易被问追问的，是为什么第二次相遇点会是入口。
核心思路
这题分两阶段：先判定链表里确实有环，再利用相遇后的距离关系定位入环点。第二阶段的结论来自 Floyd 判环的经典数学关系。
步骤讲解
1
先让快慢指针在环内相遇
和判环题一样，快指针两步、慢指针一步，若有环就会先相遇。
为什么这样做：没有第一次相遇，就谈不上后面的入环点定位。
对应代码提示：while (fast != null && fast.next != null) { ... }
2
一个指针回到头节点
相遇后，让其中一个指针重新回到 head，另一个留在相遇点。
为什么这样做：这样两者到入环点的剩余步数会相同。
对应代码提示：ListNode ptr = head;
3
两者同步前进直到再次相遇
两个指针都改成一次走一步，再次相遇的节点就是环入口。
为什么这样做：根据距离关系，头到入口距离等于相遇点再走到入口的距离。
对应代码提示：while (ptr != slow) { ptr = ptr.next; slow = slow.next; }
易错点
第一次相遇就当成入环点
快慢指针第一次相遇通常发生在环内任意位置，不一定是入口。
正确理解：相遇后还要执行“一个回头、一起一步走”的第二阶段。
无环情况没提前返回
如果链表无环，第二阶段根本没有前提，继续执行会出错。
正确理解：第一次阶段结束后如果没相遇，直接返回
null。第二阶段还让快指针走两步
这样距离关系被破坏，无法稳定落到入口。
正确理解：第二阶段两个指针都必须一次走一步。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比哈希表记录访问节点更省空间，也更符合链表题常见优化方向。
适用判断：只要链表题同时涉及环和入口/相遇位置，优先考虑 Floyd 判环扩展。
额外提醒
- 第一次相遇证明有环，第二次相遇才定位入口。
动画演示
如果你还没完全看懂，可以展开动画演示。
双指针动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
双指针动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
环形链表 II - 双指针算法
链表为空
是否有环:
否
环的入口:
无
操作日志
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。