相交链表 图解题解
两条链表可能在某处合为一体——不用哈希，两个指针互换起点就能相遇。
找两条链表的交点，就像两人分别从不同起点出发走向同一个路口：pA 走完 A 就跳到 B 头继续，pB 走完 B 就跳到 A 头继续，各自走了 lenA+lenB 步后，如果有交点两人必然同时到达那个节点——因为绕了一圈后路程相等，误差被抵消；若不相交，两人同时到达 null。
这道题到底在问什么
- 链表 A
- 4 → 1 → [8 → 4 → 5]
- 链表 B
- 5 → 6 → 1 → [8 → 4 → 5]
- 输出
- 节点 8 （A、B 共用的 8→4→5 的头）
最优解：一步一步想明白
- 3先把 A 的每个节点存进一个集合，再遍历 B、第一个已在集合里的节点就是交点。能做对，但要 O(m+n) 空间存下整条 A。
- 4转折：不用哈希。两个指针各从自己链头出发，谁走到头就跳到对方链头继续。这样 pA 走的总长是 lenA 加 lenB，pB 走的也是 lenB 加 lenA，步数完全相等——它们会同时到达交点(或同时到 null)，只用 O(1) 空间。
- 5pA 在 A 的 4，pB 在 B 的 5绿色的 [8, 4, 5] 在 A、B 里是同一批节点(只是画了两次)。pA 从 A 的头 4 出发，pB 从 B 的头 5 出发，每步各走一格。
- 6pA 在 A 的 1，pB 在 B 的 6两个指针各走一步：pA 到 A 的 1，pB 到 B 的 6。当前 pA 不等于 pB(不是同一节点)，继续。
- 7pA 在 A 的 8，pB 在 B 的 1pA 踏进绿色共用段、停在 8；pB 到 B 的 1。小心：pB 在的 1 和 A 里的 1 值一样，但它们是不同节点——必须按节点身份比，不能按值。
- 8pA 在 A 的 4(共用段)，pB 在 B 的 8pA 到共用段的 4，pB 这时才踏进绿色共用段、停在 8。两者还错着位(pA 比 pB 靠后)——因为 A 短、pA 更早进尾巴。继续走。
- 9pA 在 A 末尾 5，pB 在 B 的 4pA 走到 A 的末尾 5(A 走完了)，pB 到共用段的 4。关键转折：pA 下一步不接 null，而是跳到 B 的头去——走完自己接对方。
- 10pA 跳到 B 头 5，pB 在 B 末尾 5pA 跳到 B 的头(现在它在 B 行的 5 上)，pB 走到 B 的末尾 5。两者仍不相等：一个在 B 头、一个在 B 尾。pB 下一步也走完了 B，该跳去 A 头。
- 11pA 在 B 的 6，pB 跳到 A 头 4现在角色对称了：pB 跳到 A 的头 4，pA 在 B 上走到 6。两个指针都已经「走完一条、踏上另一条」，从此步数完全对齐。
- 12pA 在 B 的 1，pB 在 A 的 1 · 不同节点再走一步：pA 到 B 的 1，pB 到 A 的 1。又一次「值相同但身份不同」：两个 1 看着一样却不是同一节点，pA 不等于 pB，还没到交点，继续。
- 13pA 等于 pB，都在节点 8 ✓pA 走到 B 的 8、pB 走到 A 的 8——而这两个 8 是同一个节点(绿色共用段的头)！pA 共走了 5 加 3 等于 8 步，pB 也走了 6 加 2 等于 8 步，步数相等所以同时到达交点，返回它。
- 16两条不等长的链，单独看对不齐；但让每个指针都走「自己 加 对方」这同样的 m+n 长度，长度差就被自动抹平，必在第一个公共节点相遇。无需量长度、无需哈希。
- 18走完 m+n 步后 pA、pB 一起到 null两条完全不相交的链：A 长 3、B 长 2。pA 走 A 再走 B(共 5 步)落到 null，pB 走 B 再走 A(也 5 步)落到 null。两者同时变成 null，pA is pB 成立、退出、返回 null——不会死循环。
- 21练熟后去同类题迁移：LC141/142 用快慢指针的速度差制造相遇，本题用m+n 等长制造相遇——内核都是「让两指针路程相等」。想深挖可问问 AI 助教「为什么 m+n 一定能对齐」，再去通关训练里把链表双指针刷成肌肉记忆。
⚠️ 容易写错的地方
✗ 错：用 pA.val 等于 pB.val 判相交
✓ 对：用 pA is pB 判同一节点
相交是「同一个节点」，不同节点可能值相同(如本题 A、B 各有一个 1)，必须比身份不比值
✗ 错：走到头接 pA.next(自己的头)
✓ 对：走到头跳到对方的链头 headB
换成自己的头会永远错位、步数对不齐，两指针永不相遇
✗ 错：担心不相交会死循环
✓ 对：不相交时两者同走 m+n 步后一起变 null
都为 null 时 pA is pB 成立，循环正常退出、返回 null——不会死循环
完整代码（Python / C++ / Java）
Python
class Solution:
def getIntersectionNode(self, headA, headB):
pA, pB = headA, headB
while pA is not pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pAC++
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* pA = headA;
ListNode* pB = headB;
while (pA != pB) {
pA = pA ? pA->next : headB;
pB = pB ? pB->next : headA;
}
return pA;
}
};Java
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = (pA != null) ? pA.next : headB;
pB = (pB != null) ? pB.next : headA;
}
return pA;
}
}套路模板 · 双指针走两条链相遇（挖空背骨架）
pA, pB = headA, headB
while pA is not pB: # 退出条件：相遇 或 同为 None
pA = pA.next if pA else ____ # 填：走到头换对方链头 headB
pB = pB.next if pB else ____ # 填：headA
return pA # 交点 或 NoneListNode *pA = headA, *pB = headB;
while (pA != pB) { // 退出：相遇 或 同为 nullptr
pA = pA ? pA->next : ____; // 填：headB
pB = pB ? pB->next : ____; // 填:headA
}
return pA;ListNode pA = headA, pB = headB;
while (pA != pB) { // 退出：相遇 或 同为 null
pA = (pA != null) ? pA.next : ____; // 填：headB
pB = (pB != null) ? pB.next : ____; // 填：headA
}
return pA;复杂度
时间复杂度
O(m+n)
每个指针各走 m+n 步就相遇或同时到 null
空间复杂度
O(1)
只用 pA、pB 两个指针，不像哈希要存下整条 A
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 相交链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么走 m+n 步两指针一定对齐？+
pA 走 lenA 再走 lenB、pB 走 lenB 再走 lenA，总长都是 lenA+lenB。若相交，从交点起两者剩余路程相同，必在交点重合；若不相交，第 m+n 步同时变 null。
不用双指针还能怎么做？各自复杂度？+
哈希法：把 A 所有节点存集合再扫 B，O(m+n) 时间但 O(m+n) 空间。或先量两链长度、让长链先走差值步再齐步走，O(m+n) 时间 O(1) 空间。双指针是最简洁的 O(1) 空间写法。
怎么判定两条链是否相交？+
若相交，它们一定共用同一条尾巴、最后一个节点相同。也可以分别走到尾比较尾节点是否是同一个对象，相同才相交。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。