XingHuiSamaの宝藏之地

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

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

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

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

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

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

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '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：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,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
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

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

解法一：数组存储

1. 算法核心思想：逆向思维与栈结构

相交链表的拓扑结构呈现经典的“Y”字型：一旦两个链表在某一点相交，它们后续的所有节点都将完全重合。这意味着，虽然两个链表的“头部”可能不对齐（长度存在差异），但它们的“尾部”必定是完美对齐的。

采用了逆向比对的思维：通过引入 std::vector 模拟栈（Stack）的“后进先出”特性，先将原链表正向遍历并存储到数组中。随后，从两个数组的末尾（即链表的尾部）开始同步向前回溯。当遇到第一个不相同的节点时，说明到达了“Y”字型的分叉口，而在此之前记录的最后一个相同节点，即为链表相交的起始点。

2. 逻辑拆解

全量缓存（遍历装载）：分别使用两个 while 循环，遍历链表 headA 和 headB，将沿途经历的节点内存地址（指针）依次追加到动态数组 arr1 和 arr2 中。
安全倒查（出栈比对）：启动比对循环。核心循环条件 !arr1.empty() && !arr2.empty() 提供了严格的边界防护，防止在两个链表完全相同的情况下出现数组越界（段错误）。 arr1.back() == arr2.back() 用于判定当前的物理内存地址是否一致。
记录与步进：只要末尾节点相同，就将其记录到结果变量 ans 中，并通过 pop_back() 将节点剥离出数组（相当于指针向前移动一步）。当循环由于遇到不同节点而终止时，ans 中留存的即为要求的相交首节点。

3. 复杂度剖析

时间复杂度：O(M+N)。其中 M 和 N 分别为两个单链表的长度。算法需要分别完整遍历两段链表以装载数组，随后再倒序遍历公共部分。由于没有嵌套循环，总体执行耗时呈严格的线性关系。
空间复杂度：O(M+N)。为了实现倒序访问，算法额外开辟了两个数组来完整拷贝两条链表的节点指针，内存开销与两条链表的总长度成正比。

解法二

1. 算法核心思想：路径互补与状态控制

在解决相交链表问题时，由于两个链表在相交前的长度通常不同，双指针同步遍历无法同时到达交点。常见的处理思路是“路径互补”：让指针在遍历完当前链表后，继续遍历另一条链表，从而使两个指针行进的总距离对齐。

因此在路径互补的基础上，引入了明确的状态控制变量（mark 和 mark2）。通过设定状态机，限定每个指针在整个遍历过程中只能执行一次跨链表切换操作，从而避免指针在两个链表之间陷入死循环。

2. 逻辑拆解

空指针的前置检查：代码在进入 while 循环前加入了 if (pre1 == NULL || pre2 == NULL) 的判断。这是因为核心逻辑中需要通过 pre->next 探测前方节点，若直接对空指针执行 ->next 会导致程序报错退出的情况。这一步排除了空链表的边界问题。
基于标记的换轨机制：在遍历过程中，当指针到达链表尾部（即 next == NULL），且对应的状态标记为 1 时，执行换轨操作，将指针指向另一链表的头部，并将标记置为 0。
不相交情况的正常退出：如果两个链表不相交，两个指针在分别完成一次换轨（此时 mark 均为 0）后，会继续遍历至第二条链表的尾部。再次遇到 next == NULL 时，由于 mark 条件不成立，程序会进入 else 分支执行 pre = pre->next。此时两指针均被赋值为 NULL，满足 pre1 == pre2 的退出条件，正确返回 NULL。

3. 复杂度分析

时间复杂度：O(M + N)。（M 和 N 分别为两个链表的长度）。每个指针最多遍历两个链表各一次，执行次数与链表总节点数呈线性关系。
空间复杂度：O(1)。算法仅声明了常数个指针变量和整型标记变量，未占用额外的内存空间。