当前为游客只读模式。登录后可提交代码判题并保存草稿与进度。
相交链表
简单getIntersectionNode()时间限制 2000 ms内存限制 128 MB复杂度要求 时间 O(m+n),空间 O(1)
相交链表
给你两个单链表的头节点 headA 和 headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null。
题目数据保证整个链式结构中不存在环。
注意,函数返回结果后,链表必须保持其原始结构。
约定
- 相交的定义是节点引用相同(而不是节点值相同)。换句话说,当两个链表从某个节点开始共用同一段后继时,那个节点才是交点。
- 若没有交点,返回
null。 - 在本平台中,
null会被序列化为空数组[]。
输入
headA:链表 A 的头节点,用值数组表示,例如[4, 1, 8, 4, 5]headB:链表 B 的头节点,用值数组表示
输出
相交的起始节点(序列化为从该节点开始的链表值数组);若无交点,输出 []。
示例一
输入:
headA = [4, 1, 8, 4, 5], headB = [5, 6, 1, 8, 4, 5]
输出:
[8, 4, 5]
解释:链表 A 与链表 B 在节点值为 8 处开始共用同一段后继。
示例二
输入:
headA = [2, 6, 4], headB = [1, 5]
输出:
[]
解释:两个链表不相交。
示例三
输入:
headA = [], headB = [1]
输出:
[]
平台限制说明
本平台通过值数组序列化链表,无法在两条独立构建的链表之间共享同一个节点对象。因此这里的测试用例只能覆盖不相交的情形(返回 null,即 [])。参考解仍采用力扣原题的标准双指针引用比较写法,在能够构造共享节点的真实环境中同样正确。
Loading...
输入
{"args":[{"chain":[4,1],"attach":"tail"},{"chain":[5,6,1],"attach":"tail"}],"structs":{"tail":[8,4,5]}}预期输出
[8,4,5]