两个可能有环的链表求相交节点
哪些公司问过
答案要点
- 先用快慢指针分别判断每个链表是否有环并找到环入口
- 都无环:求长度差,长链先走差值再同步前进,首个相同节点为交点
- 一个有环一个无环时必不相交,因为相交后共享尾部,成环与否必一致
- 都有环:各找环入口,绕一圈能否遇到对方入口判断是否同一环
- 同一环:入口相同则以入口为终点按无环法求交,入口不同则任一入口都是交点
易错点
- 忘记排除「一环一无环」不可能相交的情况
- 都有环时只比较环入口是否相等,漏判同一环但入口节点不同的情形
- 快慢指针找环入口时步长或起点设置错误,定位错环入口
- 有环链表遍历求交时不限定范围,导致在环里死循环
面试官常见追问
- 无环链表求交点为什么能用「走到头换头」的双指针?
- 怎么找到环的入口节点?
- 如果用哈希集合来做,复杂度如何?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场