题解

题面描述

给定两个单链表的头节点 $headA$ 和 $headB$，请找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，则返回 $null$。
题目保证整个链式结构中不存在环。

输入描述：

• 第一行包含两个整数 $n$ 和 $skipA$，其中 $n$ 表示链表 $A$ 的节点个数，$skipA$ 表示在链表 $A$ 中从头节点到相交节点需要跳过的节点个数。
• 第二行包含 $n$ 个整数，表示链表 $A$ 的各节点值。

Leetcode 22.相交链表-原题链接

题目内容

给你两个单链表的头节点$headA$和 $headB$ ，请你找出并输出两个单链表相交的起始节点。如果两个链表不存在相交节点，输出 $0$ 。

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

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

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

• $intersectVal$- 相交的起始节点的值。如果不存在相交节点，这一值为 $0$
• $listA$ - 第一个链表
• $listB$ - 第二个链表
• $skipA$- 在 $listA$ 中（从头节点开始）跳到交叉节点的节点数
• $skipB$ - 在 $listB$中（从头节点开始）跳到交叉节点的节点数

输入描述

输入一共四行，

• 第一行有两个整数$n,skipA$
• 第二行为$n$个整数，表示$listA$
• 第一行有两个整数$m,skipB$
• 第二行为$m$个整数，表示$listB$

输出描述

一个整数$intersectVal$，表示相交的起始节点的值

样例1

输入

5 2
4 1 8 4 5
6 3
5 6 1 8 4 5

输出

8

说明

相交节点的值为 $8$ （注意，如果两个链表相交则不能为 $0$）。

从各自的表头开始算起，链表 $A$为 $[4,1,8,4,5]$，链表 $B$ 为$[5,6,1,8,4,5]$。

在 $A$ 中，相交节点前有 $2$ 个节点；在 $B$ 中，相交节点前有 $3$ 个节点。

— 请注意相交节点的值不为 $1$，因为在链表$A$ 和链表 $B$ 之中值为 $1$的节点 ($A$ 中第二个节点和 $B$ 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 $A$ 和链表 $B$中值为 $8$ 的节点 ($A$ 中第三个节点，$B$ 中第四个节点) 在内存中指向相同的位置。

样例2

输入

5 3
1 9 1 2 4
3 1
3 2 4

输出

2

说明

相交节点的值为 $2$ （注意，如果两个链表相交则不能为 $0$）。

从各自的表头开始算起，链表 $A$ 为$[1,9,1,2,4]$，链表$B$ 为$[3,2,4]$。

在 $A$中，相交节点前有$3$个节点；在$B$ 中，相交节点前有 $1$ 个节点。

样例3

输入

3 3
2 6 4
2 2
1 5

输出

0

说明

从各自的表头开始算起，链表 $A$ 为 $[2,6,4]$，链表 $B$ 为$[1,5]$。

由于这两个链表不相交，所以$intersectVal$ 必须为 $0$，而 $skipA$ 和 $skipB$ 可以是任意值。

这两个链表不相交，因此输出 $0$

提示

• $listA$ 中节点数目为$m$
• $listB$ 中节点数目为 $n$
• $1 <= m, n <= 3 * 10^4$
• $1 <= Node.val <= 10^5$
• $0 <= skipA <= m$
• $0 <= skipB <= n$
• 如果 $listA$ 和 $listB$ 没有交点，$intersectVal$ 为 $0$
• 如果 $listA$ 和 $listB$有交点，$intersectVal == listA[skipA] == listB[skipB]$