链表交叉和链表成环

一、基本概念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 分析查找有向无环图的汇合点任务依赖的公共父节点链表成环场景场景说明示例