面试题库 › C++ / 后端 › Y 型链表找第一个相交节点

Y 型链表找第一个相交节点

难度 ★★☆在 21 场真实面经中被问到 方向:C++ / 后端考点:链表

哪些公司问过

字节跳动5百度4腾讯2微软2寒武纪2地平线1美团1阿里巴巴1网易互娱1有赞1

常见岗位:C/C++ 软件开发、Java 后端、后端开发、iOS、推荐搜索广告

答案要点

  1. 双指针:A 走完 A 后跳到 B 的头,B 走完 B 后跳到 A 的头,相遇点即第一个相交节点
  2. 原理:两个指针总路程都是 a + c + b,相交则在交点相遇;不相交则同时走到空
  3. 时间 O(m+n),空间 O(1)
  4. 方法二:先求长度差,长链表先走差值步再同步前进
  5. 方法三:哈希集合存一个链表的节点,遍历另一个,空间 O(n)

易错点

面试官常见追问

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

相关面试题