面试题库 › 音视频 › 两个可能有环的链表求相交节点

两个可能有环的链表求相交节点

难度 ★★★在 2 场真实面经中被问到 方向:音视频考点:链表

哪些公司问过

腾讯1作业帮1

常见岗位:C++ 后端、音视频开发

答案要点

  1. 先用快慢指针分别判断每个链表是否有环并找到环入口
  2. 都无环:求长度差,长链先走差值再同步前进,首个相同节点为交点
  3. 一个有环一个无环时必不相交,因为相交后共享尾部,成环与否必一致
  4. 都有环:各找环入口,绕一圈能否遇到对方入口判断是否同一环
  5. 同一环:入口相同则以入口为终点按无环法求交,入口不同则任一入口都是交点

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题