Appearance
相交链表
更新: 7/5/2026 字数: 0 字 时长: 0 分钟
题目描述
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两条链表没有交点，返回 null。
- 相交是指节点引用相同（同一个内存节点），而不是节点值相等。
- 题目数据保证整个链表结构中不存在环。
- 函数返回结果后，链表必须保持其原始结构。
示例：
链表 A：4 → 1 → 8 → 4 → 5
链表 B：5 → 6 → 1 → 8 → 4 → 5
↑
相交起点（值为 8 的节点）链表 A 的 8 → 4 → 5 与链表 B 的 8 → 4 → 5 是同一段物理节点，相交起点是值为 8 的那个节点。
思路拆解：从暴力到最优
起点：为什么不能只比较节点值？
新手最容易踩的坑，是拿两个节点的值去比较。但相交的定义是同一个物理节点——值相同的两个节点完全可能是不同的对象。所以任何解法的判等，都必须是引用判等（pA === pB），而不是 pA.val === pB.val。
暴力解法：双重循环逐一比较
最直接的想法：对 A 的每个节点，都遍历一遍 B，看是否存在同一个节点。
点击展开暴力解法（O(m·n)）
js
function getIntersectionNode(headA, headB) {
for (let a = headA; a !== null; a = a.next) {
for (let b = headB; b !== null; b = b.next) {
if (a === b) return a // 引用相同才算相交
}
}
return null
}- 时间复杂度 ，链表较长时会明显变慢。
- 空间复杂度 ，但时间上不可接受，仅作为思路起点。
进阶：哈希集合，用空间换时间
把 A 的所有节点丢进一个 Set，再遍历 B，第一个已经在集合里的节点就是交点。判等依然是引用——Set 存的是节点对象本身。
点击展开哈希集合解法（O(m+n) 时间 / O(m) 空间）
js
function getIntersectionNode(headA, headB) {
const seen = new Set()
for (let a = headA; a !== null; a = a.next) seen.add(a)
for (let b = headB; b !== null; b = b.next) {
if (seen.has(b)) return b // 第一个命中的即为交点
}
return null
}时间降到 ，但需要额外 空间存下 A 的所有节点。还能不能把空间也省掉？
最优解：双指针「走完自己再走对方」
核心思路
让指针 pA 从 A 头出发，走到末尾后跳到 B 头继续走；指针 pB 从 B 头出发，走到末尾后跳到 A 头继续走。两个指针每一步都同时前进一格，它们要么在相交节点相遇，要么同时到达 null。
为什么一定会相遇？ 设 A 独有部分长度为 、B 独有部分长度为 、公共尾部长度为 。
pA走过的路径长度为：（先走完 A，再走 B 的独有部分）pB走过的路径长度为：（先走完 B，再走 A 的独有部分）
两者都等于 ！也就是说，两个指针走了相同的总步数后，会同时到达公共尾部的起点——这正是相交节点。若两链不相交（），它们会在走完 步后同时变成 null，循环自然结束，返回 null。
交互动画演示
下面的动画完整还原了双指针「走两条链」的每一步：蓝色是 pA、红色是 pB，绿色是共享（相交）尾部。点击 ▶ 自动播放，观察两个指针如何在值为 8 的节点相遇。
双指针 · 相交链表演示
链表 A：
4 → 1 → 8 → 4 → 5；链表 B：5 → 6 → 1 → 8 → 4 → 5；共享尾部从值 8 起 当前阶段：准备
链表 A
4
→pA
1
→8
→4
→5
→ null
链表 B
5
→pB
6
→1
→8
→4
→5
→ null
指针 pA指针 pB共享（相交）节点相遇
两个指针 pA、pB 分别从链表 A、链表 B 的头部出发，每次各走一步。
步骤 0 / 11
完整代码
js
function getIntersectionNode(headA, headB) {
if (!headA || !headB) return null // 任一为空则不可能相交
let pA = headA
let pB = headB
// pA、pB 相等时（同一节点或同为 null）跳出循环
while (pA !== pB) {
// 走到末尾就跳到另一条链的头部；否则正常前进一步
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return pA // 相交节点；若不相交，此时 pA === pB === null
}易错点
第 7–8 行的跳转条件是「当前节点是否为 null」，即 pA === null ? headB : pA.next。必须先判断 null 再决定下一步，而不能写成 pA.next === null ? headB : pA.next——后者会让指针少走一格（跳过了各自的 null 位置），破坏「总步数相等」的前提，导致不相交时陷入死循环。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力双重循环 | 每个 A 节点都扫一遍 B | ||
| 哈希集合 | 存下 A 的所有节点引用 | ||
| 双指针（最优） | 两指针各走 步相遇 |
其中 、 分别为链表 A、B 的长度。双指针法在时间与空间上都达到最优。
边界与易错点
- 不相交的情况：当 ，两指针会在走完 步后同时变为
null，此时pA === pB === null，循环退出返回null——无需任何额外判断。 - 任一链表为空：
headA或headB为null时不可能相交，可提前返回null（第 2 行）。即使不提前返回，while条件也能正确处理，但提前返回更清晰。 - 两链等长：若 ，两指针在第一趟就可能相遇，跳转分支不会触发，逻辑依然正确。
- 判等用引用而非值：全程用
pA !== pB判断，切勿改成比较.val。 - 循环终止性：正因为两指针路径总长严格相等，它们必然在有限步内相等（相遇或同为
null），不会死循环——前提是跳转条件写对（见上方 warning）。
一句话总结
两个指针「走完自己的路，再走对方的路」，就把长度差抹平了——殊途同归，终会在交点相遇。