当前为游客只读模式。登录后可提交代码判题并保存草稿与进度。

相交链表

简单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]
自定义用例