题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
简单
相关标签
premium lock icon相关企业
提示

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构

 

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。

 

提示:

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listAlistB 没有交点,intersectVal0
  • 如果 listAlistB 有交点,intersectVal == listA[skipA + 1] == listB[skipB + 1]

 

进阶:你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案?

通过次数
304,407/452K
通过率
67.3%


icon
相关企业

提示 1
你可以在O(A + B)的时间和额外的O(1)空间中做到这一点,也就是说,你不需要一个散列表(尽管你可以用一个散列表来完成)。

提示 2
举例子能帮到你。画一个相交的链表和两个不相交的等价链表(值)的图片。

提示 3
首先要确定是否有交叉点。

提示 4
注意,两个相交链表的最后节点始终相同。一旦它们相交,之后的所有节点将相等。

提示 5
你可以通过遍历到每个链表的末尾并比较它们的尾节点来确定两个链表是否相交。

提示 6
现在,你需要查找链表在何处相交。假设链表长度相同。你可以怎么做?

提示 7
如果两个链表长度相同,则可以在每个链表中向前遍历,直到找到一个公共的元素。现在,面对长度不同的链表,你该怎样调整?

提示 8
尝试使用两个链表长度之间的差异。

提示 9
如果你通过长度差异向较长的链表中移动指针,则可以在链表相同时应用类似的方法。

评论 (0)

《程序员面试金典(第 6 版)》独家授权
本书是原谷歌资深面试官的经验之作,帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的,帮助你轻松应战 IT 名企技术面试。
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
intersectVal =
8
listA =
[4,1,8,4,5]
listB =
[5,0,1,8,4,5]
skipA =
2
skipB =
3
Source