Y 型链表找第一个相交节点
哪些公司问过
答案要点
- 双指针:A 走完 A 后跳到 B 的头,B 走完 B 后跳到 A 的头,相遇点即第一个相交节点
- 原理:两个指针总路程都是 a + c + b,相交则在交点相遇;不相交则同时走到空
- 时间 O(m+n),空间 O(1)
- 方法二:先求长度差,长链表先走差值步再同步前进
- 方法三:哈希集合存一个链表的节点,遍历另一个,空间 O(n)
易错点
- 指针走到空之后没有切换到另一个链表
- 把相交理解为值相等,而不是节点是同一个
- 循环条件写错,不相交时死循环
- 忘了处理链表为空的情况
面试官常见追问
- 为什么两个指针一定会在交点相遇?
- 怎么判断两个链表是否有环、是否相交?
- 只知道要删除的节点地址,没有前驱,怎么删?
- 如何求链表的长度差?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场
- 旋转链表:向右移动 k 位8 场