链表专题(五)：殊途同归——「相交链表」
场景想象：
有两条路（链表 A 和链表 B），它们在某个路口（交点 Node）汇合了，变成了一条路（Y 字形结构）。
路 A：
a1 -> a2 -> c1 -> c2 -> c3（长度 5）路 B：
b1 -> b2 -> b3 -> c1 -> c2 -> c3（长度 6）交点：
c1。
核心痛点：
如果两条路长度一样，那简单，两个指针一起走，走到相同节点就是交点。
但现在 A 短 B 长。
指针 A 走到
c1时，指针 B 还在b3。它们完美错过了，永远遇不到。
怎么让它们在终点相遇？必须抹平长度差。
力扣 160. 相交链表
https://leetcode.cn/problems/intersection-of-two-linked-lists/
题目分析：
输入：
headA,headB。目标：找到两个链表相交的起始节点。如果不相交，返回 null。
输出：交点 Node。
核心思维：指针拼接 (A + B = B + A)
我们不需要去算长度差 lenA 和 lenB。
有一个更巧妙的办法：
指针 pA：先走链表 A，走完了，直接跳到链表 B 的头接着走。
指针 pB：先走链表 B，走完了，直接跳到链表 A 的头接着走。
奇迹发生了：
pA 走的路程：
A 的前缀+公共部分+B 的前缀pB 走的路程：
B 的前缀+公共部分+A 的前缀路程完全相等！它们一定会在第二次遍历时，在交点处（或者终点 null 处）相遇。
代码实现 (JavaScript)
JavaScript
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { if (!headA || !headB) return null; let pA = headA; let pB = headB; // 只要两个指针没相遇，就一直跑 // 如果相交，它们会在交点相遇 // 如果不相交，它们会同时走到 null (null === null 退出循环) while (pA !== pB) { // 核心逻辑：走完了自己，就去走对方的路 // 如果 pA 走到头了 (null)，就跳到 headB；否则前进一步 pA = pA === null ? headB : pA.next; // 如果 pB 走到头了 (null)，就跳到 headA；否则前进一步 pB = pB === null ? headA : pB.next; } // 退出循环时，pA 就是交点（或者 null） return pA; };深度模拟
假设：
A: 1 -> 2 -> 8 -> 9 (长度4)
B: 3 -> 8 -> 9 (长度3)
交点是 8。
Round 1:
pA: 1, pB: 3
Round 2:
pA: 2, pB: 8
Round 3:
pA: 8, pB: 9
Round 4:
pA: 9, pB: null (pB 走完了，跳到 A) -> pB 现在指向 1
Round 5:
pA: null (pA 走完了，跳到 B), pB: 2 -> pA 现在指向 3
Round 6:
pA: 8, pB: 8
相遇！返回 8。
总结
这道题的代码极简，但背后的思维非常巧妙。
面试官问：如果不能修改链表结构（不能翻转），且空间复杂度要求 $O(1)$（不能用 Set 存节点），怎么做？
标准答案：就是这种**“双指针拼接”法。记住这个浪漫的套路：“我走完我的路，就去走你的路。”**
下一题预告：环形链表 II
好了，链表进阶篇的最后一关：LC 142. 环形链表 II（专题六）。
题目：给定一个链表，如果它有环，请找到入环的那个节点。
难点：判断有环很简单（快慢指针追击），但怎么找到入口？
这又是一道数学推导题。你需要证明：当快慢指针相遇时，再派一个指针从头开始走，它和慢指针会在入口处相遇。
这是双指针链表题的最终 Boss，准备好做点数学题了吗？🔢