你好！我是你的 OI 教练。今天我们要攻克链表专题中一个非常精妙的题目：相交链表。

这道题在 LeetCode 上是基础题，但在 NOI 竞赛中，它常作为考察双指针逻辑推导和空间复杂度极限优化的范例。

一、 预备知识点 checklist

1. 链表物理结构：理解链表节点在内存中的独立性。相交是指两个指针指向了同一个内存地址，而不仅仅是数值相等。
2. 双指针算法：掌握如何通过指针的同步或异步移动来对齐数据长度。
3. 距离抵消思想：这是解决本题的核心数学逻辑。

二、 题目描述：相交链表 (Intersection of Two Linked Lists)

题目描述： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示说明：若两个链表相交，其形状必然呈 “Y” 字型，即从相交点开始，之后的所有节点都是共享的。

输入格式 (Standard Input)：

• 第一行包含五个整数：intersectVal（相交节点的值），listA_len（链表 A 长度），listB_len（链表 B 长度），skipA（A 中跳过多少个节点开始相交），skipB（B 中跳过多少个节点开始相交）。
• 第二行包含 listA_len 个整数。
• 第三行包含 listB_len 个整数。
• 注：若 intersectVal 为 0，表示不相交。

输出格式 (Standard Output)：

• 若相交，输出：Intersected at val（其中 val 为相交节点的值）。
• 若不相交，输出：No intersection。

样例输入 1：

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

样例输出 1：

Intersected at 8

数据规模与约定：

• $n, m \le 3 \times 10^4$ （分别为两个链表的长度）
• $-10^9 \le \text{节点值} \le 10^9$
• 时间限制：1.0s
• 内存限制：128MB
• 核心挑战：时间复杂度 $O(n+m)$，空间复杂度 $O(1)$。

三、 教练的草稿纸：启发式推理过程

为什么这道题难？因为两个链表相交前的“前缀”长度可能不一样。

1. 暴力思路的局限

• 遍历 A 的每个节点，再去遍历 B 的每个节点看地址是否一样。
• 复杂度 $O(n \times m)$。在 $3 \times 10^4$ 数据规模下会超时（$9 \times 10^8$ 次运算）。

2. 长度对齐法（思路 A）

• 计算 A 长度 $L_1$，B 长度 $L_2$。
• 让长的那个链表先走 $|L_1 - L_2|$ 步。
• 现在两个指针到终点的距离一样了，同步走，碰撞点即为相交点。

3. 浪漫的“交换人生”法（思路 B - 最优解）

这是 OI 中非常浪漫的一个算法：

• 定义指针 pA 从 A 出发，pB 从 B 出发。
• pA 走完 A 后，立即跳到 B 的头开始走。
• pB 走完 B 后，立即跳到 A 的头开始走。
• 数学原理：
  • pA 走的路径总长：$L_1 + L_{B\_before\_intersect}$
  • pB 走的路径总长：$L_2 + L_{A\_before\_intersect}$
  • 显然 $L_1 + (L_2 - \text{common}) = L_2 + (L_1 - \text{common})$。
  • 它们会在相交点准时相遇！如果不相交，它们会同时指向 null（长度均为 $L_1 + L_2$）。

四、 算法流程图 (Mermaid 风格)

graph TD
    A("开始处理") --> B("初始化 pA 指向 headA, pB 指向 headB")
    B --> C{"pA 等于 pB 吗?"}
    
    C -- "是 (找到相交或同时为空)" --> D("返回 pA")
    C -- "否" --> E{"pA 是否为空?"}
    
    E -- "是 (走到 A 尽头)" --> F("pA 转向 headB")
    E -- "否" --> G("pA 移动到下一个节点")
    
    F --> H{"pB 是否为空?"}
    G --> H
    
    H -- "是 (走到 B 尽头)" --> I("pB 转向 headA")
    H -- "否" --> J("pB 移动到下一个节点")
    
    I --> C
    J --> C
    
    D --> K("结束")

五、 复杂度分析思考过程

• 时间复杂度分析：

  • 每个指针最多遍历 $L_1 + L_2$ 个节点。
  • 对于 $3 \times 10^4$ 的数据，总步数约 $6 \times 10^4$，远低于 $10^8$ 的限制。
  • 结论：$O(n+m)$。

• 空间复杂度分析：

  • 我们只定义了两个辅助指针 pA 和 pB。
  • 没有使用 std::set 或额外的数组。
  • 结论：$O(1)$。

六、 读题关键词与坑点总结

1. “相交”定义：

   • 关键词：“同一个节点”。
   • 注意：如果两个链表的值序列是 1-2-3 和 4-2-3，值虽然有重复，但不一定是同一个节点。必须是内存地址相等。

2. “不修改链表结构”：

   • 关键词：“保持原始结构”。
   • 注意：有些技巧（如临时把 A 链表连成环）虽然能解题，但如果题目要求不修改结构，必须在返回前恢复。

3. “$O(1)$ 内存”：

   • 这是强制你放弃哈希表的信号。

4. $pos$ 相关参数：

   • 这是出题人为了构造数据给的，解题时不可直接利用这些变量。

教练建议

在 NOI 笔试或初赛中，这类题目经常考察指针相遇的条件。记住那个核心等式：$a + c + b = b + c + a$（其中 $c$ 为公共部分）。这不仅是一个算法，更是一种消除个体差异、寻找共同终点的数学美学。加油！