环形链表找环入口及公式推导
哪些公司问过
答案要点
- 快慢指针判环:慢走一步、快走两步,相遇则有环
- 相遇后一个指针回到头部,两者同速前进,再次相遇处即入口
- 设头到入口 a、入口到相遇点 b、环长 c,有 2(a+b)=a+b+nc
- 推出 a=(n-1)c+(c-b),即头到入口距离等于相遇点到入口距离加整圈
- 时间 O(n),空间 O(1)
易错点
- 快指针移动前没判断 fast 和 fast.next 是否为空
- 以为相遇点就是环入口
- 推导时忽略快指针可能已绕环多圈
面试官常见追问
- 为什么慢指针在第一圈内就会被追上?
- 怎么求环的长度?
- 用哈希表怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场