intersection · Y 形相交

两链表相交：找第一个公共节点

两条单链表如果相交，会从某个节点起共用同一段尾部（是同一批节点，不是值相等而已）——形状像个 Y。问题：它们相不相交？若相交，第一个公共节点是谁？设 A 独有段长 a、B 独有段长 b、公共段长 c。朴素法要么暴力两两比较 $O(ab)$ 、要么用 HashSet 存 A 全部节点再扫 B（ $O(a+c)$ 空间）。下面两种 $O(1)$ 空间的双指针法，都在消除「长度差」这个障碍。

换轨法为什么成立:pA 走完 A（长 a+c）再从 B 头接着走，pB 走完 B（长 b+c）再从 A 头走。两者走到第一个公共点时，各自都恰好走了 a+c+b 步——步数被拉齐，于是同时到达、在该点相遇。不相交时两者会同时走到 null（各走 a+b 步）,pA === pB === null 照样成立，返回 null。这就是为什么循环写 pA = pA ? pA.next : headB 而不能跳过 null 直接续——null 那一拍正是拉齐长度的关键。

只判断「是否相交」更简单：无环时，只要两条链的尾节点是同一个（比较引用，非值），就相交，否则不相交—— $O(a+b)$ 一趟到尾。长度对齐法则先各扫一遍得长度，让长的那条先走 $|lenA-lenB|$ 步抹平差距，再齐步同行，第一次指向同一节点即公共点。带环的相交更复杂：先各自 Floyd 判环，再按「都无环 / 都有环 / 一有一无（不可能相交）」分情形讨论。