适用读者：会写快慢指针，但第一次看到「交换游标」这个操作觉得像是变魔术的人
技术栈：Python 为主，附 Java 版
难度：简单（代码只有 5 行，但"为什么这样能对上"值得想清楚）
收获：a + c + b == b + c + a 这个同构替换，以及它为什么天然给出 O(1) 空间
题目
给你两个单链表的头节点
headA 和
headB，请你找出并返回两个单链表相交的
起始节点。如果两个链表不存在相交节点，返回
null。
图示两个链表在节点
c1 开始相交：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
题目数据
保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须
保持其原始结构。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
：你能否设计一个时间复杂度
O(n + m)、仅用
O(1) 内存的解决方案？
出处备注：字节、阿里等面试中作为链表基础题频繁出现，通常紧跟"两数之和"式的热身出现，用来考察你能不能把"两个不等长的序列对齐"这件事转化成一行代码。
链表节点的定义（后面所有代码都用它）：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
一、先想清楚「相交」到底是什么意思
1.1 相交的判据是节点，不是值
这是这题最容易踩的第一个坑。看这个例子：
A: 1 → 2 → 3
B: 5 → 3 → 6
两个链里都有
3，它们相交吗？
不相交。 那是两个不同的节点，只是值恰好都是 3。
A: 1 → 2 ─┐
↓
3 → 4 → 5
↑
B: 6 → 7 ─┘
这个才叫相交 —— 两条链从节点
4 开始
共享同一批节点，
next 指针指向的是同一个对象。
A: 1 → 2 → 3 → 4 → 5
↗
B: 6 → 7
注意这是一个 Y 字形，不是 X 字形。两个单链表一旦相交，后面就必须完全重合——因为每个节点只有一个 next。这是单链表的结构决定的，也是一个很重要的直觉。
所以"相交起始节点"的定义是：两条链第一次汇到同一个节点上的那个节点。 换句话说：两条链共享的那段
后缀的起点。
1.2 朴素解法为什么不够好
你可能会想到两种做法：
做法一：哈希表。 先遍历 A，把所有节点塞进
set，再遍历 B，第一个命中的就是答案。
def getIntersectionNode(headA, headB):
seen = set()
cur = headA
while cur:
seen.add(cur)
cur = cur.next
cur = headB
while cur:
if cur in seen:
return cur
cur = cur.next
return None
时间
O(n + m)，但空间
O(n) —— 不满足进阶要求。
做法二：先算长度差。 分别量出两条链的长度
lenA、
lenB，让长的先走
|lenA - lenB| 步，然后两个指针同步前进，第一个相等的节点就是答案。
def getIntersectionNode(headA, headB):
lenA, lenB = length(headA), length(headB)
# 长的先走差值，对齐到"距离末尾一样远"
...
时间
O(n + m)，空间
O(1) ——
完全正确，而且很直观。这是标准答案之一。
但要让短的指针从
头出发、长的先走一段，代码里得有分支判断谁长谁短，还要写两遍几乎一样的循环，约 20 行。
1.3 核心洞察：让两个指针走一样长的路
先看一个更简单的视角。
要让两个指针同时到达相交点，需要它们
距离末尾一样远。做法二就是硬把这件事做出来：让长的先走一段。
而接下来这个做法，连"谁长谁短"都不用判断：
pA 从 A 的头出发，走完 A 就去走 B 的头；
pB 从 B 的头出发，走完 B 就去走 A 的头。
两者每次各走一格。
设 A 的独有段长度是
a、B 的独有段长度是
b、公共段长度是
c：
A: a1 → a2 → ... (a 个)
↘
c1 → c2 → ... (c 个)
↗
B: b1 → b2 → ... (b 个)
- pA 走的路：A 的独有段
a 步 + 公共段 c 步 + B 的独有段 b 步 = a + c + b
- pB 走的路：B 的独有段
b 步 + 公共段 c 步 + A 的独有段 a 步 = b + c + a
这两个数是同一个数。 加法交换律 —— 就这么简单。
路程相等、速度相等（都是一次一格），出发时间相同，那么它们
必然同时到达终点。而那个"终点"就是相交点：
pA: a1 → a2 → c1 → c2 → b1 → b2 → [c1] ← 走 a+c+b 步后停在 c1
pB: b1 → b2 → c1 → c2 → a1 → a2 → [c1] ← 走 b+c+a 步后也停在 c1
↑
同时落在 c1
pA 的路： A独有(a) ──→ 公共(c) ──→ B独有(b)
pB 的路： B独有(b) ──→ 公共(c) ──→ A独有(a)
↑
两条路长度都用 a+b+c 表示
—— 不用判断谁长谁短，不用分支，不用写两遍循环。
同理，如果两条链不相交（
c = 0），两者各走
a + b 步后
同时到达 null —— 于是返回
null。不相交的情况也被同一套逻辑自然地覆盖了。
二、这个想法的代码只有五行
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
pA, pB = headA, headB
while pA is not pB: # 比的是"是不是同一个节点"，不是值
pA = pA.next if pA else headB # 走完 A 就换到 B 的头
pB = pB.next if pB else headA # 走完 B 就换到 A 的头
return pA # 要么是相交点，要么是 None
是的，就这么多。
整个算法的全部内容就是"走到头就换到对方头上"。
2.1 为什么循环条件写 while pA is not pB
因为两个指针
一旦相等就一定是答案，而且这个"相等"有两种可能：
- 相交：两者同时落在相交起始节点上 —— 返回它；
- 不相交：两者同时变成
None —— None is None 成立，循环退出，返回 None。
第二种情况是这段代码最漂亮的地方：
不用为"不相交"写任何特判。两条链不相交时，两个指针会在走满
a + b 步后手拉手一起掉出链表，
pA is pB 恰好成立。
用
!== 或
!= 对比值就错了 —— 值相同的不同节点会被误判成相交（见 1.1）。
2.2 为什么"换头"这个操作是合法的
pA = pA.next if pA else headB 这一行里，
pA 从 A 的尾节点（它的
next 是
None）直接跳到了
headB。
这在题目里
完全合法：
- 题目只要求"函数返回结果后链表保持原始结构"。我们没有改任何
next 指针，只是让一个指针变量指向了另一个链表的头 —— 这是读操作，不是写操作；
- 所以不需要像 LC 143 重排链表那样小心翼翼地拆链条、防成环。这里自始至终是两棵独立的链，一个指针从这棵跳到那棵，不产生任何环。
顺带说一句：这也解释了为什么这题空间是 O(1) —— 我们只多了两个指针变量。
2.3 换个角度理解：把两条链首尾相接
还有一个更"几何"的看法，很多人觉得更好记：
把 A 的尾巴接到 B 的头上，把 B 的尾巴接到 A 的头上：
A: a1 → a2 → c1 → c2 → b1 → b2 → (回到 A 头)
B: b1 → b2 → c1 → c2 → a1 → a2 → (回到 B 头)
这两条
串起来的新链长度相等（都是
a + b + c），而且它们从各自位置出发、"同步前进"的指针，第一次重合的位置一定是
c1。
不过这个说法要小心一点：如果真的去改尾节点的
next，就
破坏了原始结构（还制造了环）。所以它只是个理解用的心智模型，
代码里千万别真去接。实际做法就是"指针变量换目标"，不碰链表本身。
三、动画：看着两条路同时走到 c1
下面这个动画把过程拆成 11 帧。留意三件事：
- 两条链画成 Y 字：A 在上、B 在下，各自的独有段从左右两端出发，在同一个节点上合并成一条 —— 共享的那段节点只画一次，因为它们在内存里就是同一个节点；
- 两个游标同步前进：pA 和 pB 每帧各走一格，永远不同步落在同一个节点上，直到最后一帧；
- 换头那一帧：走到 ∅ 的游标，会有一条虚线从尾节点绕到对方链表的头上 —— 那是整套解法里唯一一个"反直觉的动作"，值得单独停一帧看清楚。
看完动画再回头看 1.3 节那张"两条路"的对比图 —— 画面上就是两个游标各自绕了一圈，最后
同时落在
4 上。
四、完整推演表
用动画里的例子（
a = 3、
b = 2、
c = 2）：
pool 下标: 0=1 1=2 2=3 3=4 4=5 5=6 6=7
A = 1 → 2 → 3 → 4 → 5 独有段 1→2→3，公共段 4→5
B = 6 → 7 → 4 → 5 独有段 6→7，然后并到同一个 4 上
数一下：pA 走了 A 的 5 步 + B 上的 2 步 =
7 步；pB 走了 B 的 4 步 + A 上的 3 步 =
7 步。
a + b + c = 3 + 2 + 2 = 7，正好对上。
两个游标的总步数相等 —— 这就是它们必然同时到达的原因。
再看不相交的例子
A = [1,2,3]、
B = [4,5]：
注意第 7 步：两者
同时变成空 ——
while pA is not pB 检测到
None is None，循环退出，返回
None。这里一步特判都不需要。
五、Java 版
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) { // 比引用，不是比值
pA = (pA == null) ? headB : pA.next; // 走完 A 就换到 B 的头
pB = (pB == null) ? headA : pB.next; // 走完 B 就换到 A 的头
}
return pA; // 相交点，或 null
}
}
Java 里用
!= 比引用正是我们想要的语义（而
!equals 才是比值）。这一点 Python 和 Java 是一致的：
这题要的永远是引用比较。
六、边界情况
几个要记牢的：
- 空链表安全。
headA is None 时循环不执行，直接返回 None。不需要额外特判（Java 版里那句 if (headA == null || headB == null) 是防御性的写法，去掉也能跑对）。
- 值相同不算相交。这是这题最经典的错误答案，务必在面试里主动提一句"我比的是引用"。
- 完全同一条链是最快的情况：头节点就相等，0 轮循环。
七、复杂度
- 时间
O(n + m)：两个指针各走 a + b + c 步，最多 n + m 步（n、m 是两条链各自的长度）。每一轮循环里两个指针各前进一格，是常数工作量。
- 空间
O(1)：只有 pA、pB 两个指针变量，没有任何数组、哈希表、递归栈。
对比一下哈希表方案：时间同样是
O(n + m)，但空间
O(n) —— 进阶要求写在题干里，就是为了排除掉它。
八、常见坑
1. 用值比较，不用引用比较。
while pA.val != pB.val: # 错的！值相同的不同节点会被误判
这是最致命的错误。
1.1 节那个
A: 1→2→3 /
B: 5→3→6 就是专门用来打这个的。
任何时候，链表的"是不是同一个节点"都必须用 is / == 比引用。
2. 换头那行写成 pA = pA.next if pA.next else headB。
pA = pA.next if pA.next else headB # 错的！会漏掉最后一格
if pA 判的是
"pA 自己是不是 None"，也就是"我是不是已经走出链表了"。写成
pA.next 就变成了"我下一个是不是空"，会在最后一个真实节点上就提前换头 —— 少走一格，两条路就不等长了。
3. 循环条件写 while pA and pB。
while pA and pB: # 错的！不相交时会死循环地空转
因为不相交时两者
会同时变成 None，
pA and pB 立刻为假，循环退出 —— 看起来"能用"，但它丢掉的是"相交判定"本身：
pA is not pB 才同时表达了"还没相遇"和"还没同时出界"。
4. 忘了这题允许"指针跨链"，以为要改链表。
有人看到"让 pA 走 B"就以为要把 B 接到 A 的尾巴上。
不要改任何 next。 题目明确要求保持原始结构，而且真接了会制造环。换个指针指向就行。
5. 想当然地认为两条链长度相同时才"好办"。
长度相同确实更简单（同时出发，走到第一个相同节点就是答案），但算法对长度不等
天然成立 —— 这正是
a + c + b == b + c + a 的价值。不要额外加长度相同的特判。
九、面试怎么答
开口 30 秒给思路（别一上来就写代码）：
目标是让两个指针同时到达相交点。做法是：pA 从 A 出发，走完 A 就接着走 B；pB 从 B 出发，走完 B 就接着走 A。这样 pA 走 A独有 + 公共 + B独有，pB 走 B独有 + 公共 + A独有，两个数相等，所以它们必然同时到达 —— 那个位置就是相交点。如果不相交，两者会同时走到 null。时间 O(n+m)，空间 O(1)。
然后主动交代两个关键点 —— 这是区分"背过答案"和"真懂"的地方：
- 比的是引用不是值。值相同的不同节点不算相交；
- 换头不破坏链表结构。只是指针变量的目标变了，没有动任何
next，所以不产生环，也满足"保持原始结构"的要求。
追问应对：
- "为什么不相交时不用写特判？" —— 因为两个指针会在走满
a+b 步后同时变成 None，while pA is not pB 恰好成立，循环自然退出。
- "能讲讲你已经知道的那种长度差解法吗？" —— 能：先各量一遍长度，长的先走差值，再同步前进。也是 O(n+m)/O(1)，但要判断谁长谁短、循环写两遍。交换游标版没有分支，所以更短。
- "如果链表可能成环呢？" —— 那这题的前提就破了：相交起始节点在带环图里定义不唯一。得先做 LC 141/142 那套判环找入口，再谈相交。
- "能不能不改变链表结构？" —— 已经没改。真要说的话，长度差解法同样不改结构，两者在这点上都合规。
结语
把链表系列串起来看，这题的位置是这样的：
这题的优雅之处在于：
它把"对齐两个不等长的序列"这件麻烦事，变成了"两条路本来就一样长"。
pA 的路： A独有(a) → 公共(c) → B独有(b) = a + b + c
pB 的路： B独有(b) → 公共(c) → A独有(a) = a + b + c
下次再遇到"两个指针要走一不一样长的路"这类问题，先问自己一句：
能不能各走一段对方的？ 如果能，加法交换律会替你把剩下的事做完。