一、基本概念
1. 链表交叉（Intersection of Linked Lists）
定义：两个链表在某个节点处汇合，之后共享同一段链表（呈 Y 字形或倒 Y 字形）。
text
链表A: a1 → a2 → a3 → a4 → a5 ↓ 链表B: b1 → b2 → b3 → b4 → a4 → a5 ↑ 交叉点
关键特征：
从交叉点开始，两个链表完全重合
交叉点只有一个（不可能出现 X 形交叉，因为节点只有一个 next 指针）
2. 链表成环（Cycle in Linked List）
定义：链表中某个节点的 next 指针指向了之前的某个节点，形成闭环。
text
单向链表: 1 → 2 → 3 → 4 → 5 → 6 ↑ ↓ 9 ← 8 ← 7 (环入口：4)
关键特征：
环入口是环中第一个被访问的节点
遍历链表会无限循环（永远走不到 null）
二、特点对比
| 特性 | 链表交叉 | 链表成环 |
|---|---|---|
| 涉及链表数 | 2 个或以上 | 1 个 |
| 数据结构特征 | Y 形（共享尾部） | 环形（尾部指向内部节点） |
| 遍历终止条件 | 可到达 null（不交叉的尾部） | 永远到不了 null |
| 唯一性 | 交叉点唯一 | 环入口唯一 |
| 内存特征 | 两个链表共享节点 | 单链表自我引用 |
| 检测方法 | 双指针/哈希表/长度差 | Floyd 快慢指针/哈希表 |
三、详细对比
| 对比维度 | 链表交叉 | 链表成环 |
|---|---|---|
| 核心问题 | 找交叉点 | 检测环 + 找环入口 |
| 时间复杂度 | O(m + n) | O(n) |
| 空间复杂度 | O(1)（最优） | O(1)（最优） |
| 异常情况 | 无交叉（返回 null） | 无环（返回 null） |
| 主要算法 | 长度差法、双指针法 | Floyd 快慢指针 |
| 变体问题 | 多链表交叉 | 环长度、环入口位置 |
四、使用场景
链表交叉场景
| 场景 | 说明 | 示例 |
|---|---|---|
| 版本控制 | 两个分支合并点 | Git 分支合并的公共祖先 |
| 社交网络 | 共同好友交集 | 两个用户的共同关注人 |
| 数据去重 | 判断两个数据集是否共享 | 缓存系统共享公共前缀 |
| DAG 分析 | 查找有向无环图的汇合点 | 任务依赖的公共父节点 |
链表成环场景
| 场景 | 说明 | 示例 |
|---|
