LeetCode题解-链表标签:链表相交
题目:给定两个(单向)链表,判定它们是否相交并返回交点。请注意相交的定义基于节点的引用,而不是基于节点的值。换句话说,如果一个链表的第k
个节点与另一个链表的第j
个节点是同一节点(引用完全相同),则这两个链表相交。
示例 1
:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 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
输出:Reference of the node with value = 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
。
注意:
如果两个链表没有交点,返回 null
。
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n)
时间复杂度,且仅用 O(1)
内存。
来源:力扣(LeetCode
)
链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:若两个链表相交,那么情况一定是如下图所示:
相交的节点后面,两个链表完全重合,那么如何找到相交的节点呢?如果两个链表长度一样,那么同时遍历两个链表,当遇到引用相等的节点时就是两个链表相交的节点。但如果两个链表长度不一样呢?假设我们能够基于两个长度不同的链表构造出长度一样的两个链表,那么就可以找到相交的节点。那问题转换成如何构造长度一样的链表?如果两个链表的长度相差x
个节点,先用一个指针遍历较长的链表x
次,这时如果将该指针指向的节点作为头节点,跟另一个较短长度的链表就构成了长度一样的两个链表。然后同时进行遍历,直到遇到引用相等的节点即为头节点。如果整个过程都未遇到引用相等的节点,则可断定两个链表不相交。
代码如下:
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |