LeetCode LCR 023. 相交链表
目录
题目描述
题意分析
给两条单链表的头节点
headA、headB，返回它们第一个公共节点；不相交返回空。「公共」指的是同一个节点对象，比较的是引用而非节点值。关键的结构性事实藏在链表定义里：每个节点只有一个
next。一旦两条链在某个节点汇合，此后的路径就完全重合，再也分不开。所以两条链的形状必然是「Y 字形」——各自一段独占前缀，然后共享同一条公共后缀。这意味着公共节点一定是从尾部往前对齐的，两条链的公共部分长度相同。难点全在长度不等上：两条链的独占前缀长度不同，直接从两个头同时往后走会永远错位，看似需要先量长度。
题目还要求不能改动链表结构，进阶要求 $O(1)$ 空间和 $O(m+n)$ 时间，所以「把 A 的所有节点扔进哈希集合再扫 B」虽然直观，但不是最终目标。
边界：任一条链为空则不可能相交；两条链完全相同（同一个头）时答案就是头节点；不相交时必须返回空而不是任意节点。
解法：双指针收缩边界
核心思路
暴力有两种。一是把 A 的节点全放进哈希集合，再顺着 B 找第一个命中的，$O(m+n)$ 时间但 $O(m)$ 空间。二是先各走一遍量出长度
m、n，让长的那条先走|m-n|步补齐差额，然后同速前进，第一次相等即答案——这个做法已经是 $O(1)$ 空间，但要写「求长度 + 判断谁长 + 补步数」三段代码，白板上容易写岔。瓶颈在于「补齐长度差」这件事被显式地算了出来。观察第二种做法的本质：我们想让两个指针走过的总路程相等，这样它们才能同时抵达公共段的起点。而总路程相等有一个不需要计算的实现方式——让每个指针都把两条链各走一遍。
具体地，指针
a走完 A 之后接着从headB继续，指针b走完 B 之后接着从headA继续。设 A 的独占前缀长x、B 的独占前缀长y、公共段长z。a到达公共段起点时走了x + z + y步，b到达时走了y + z + x步，两者完全相等，所以它们必然在公共段起点同时到达，此刻a == b。不变量因此可以表述为：两个指针任意时刻走过的总步数相同；由于两条路径的总长都是
x + y + z，它们要么在公共段起点相遇，要么同时走到路径尽头。不相交的情况天然被覆盖：此时
z = 0，a走完x + y步后为空，b走完y + x步后也为空，两者同时变成null，循环条件a != b因null == null而结束，返回空正好是答案。这一点是这个写法最漂亮的地方——不相交不需要任何特判。
解题步骤
- 初始化：
a = headA，b = headB，两个指针各自从自己的链头出发。- 循环条件写
a != b：既作为「找到公共节点」的成功出口，也作为「双双为空」的失败出口。用引用比较而不是值比较，因为题目定义的相交是同一个对象。- 推进规则：
a = (a == null ? headB : a.next)，b = (b == null ? headA : b.next)。判空写在取next之前，含义是「走到尽头就切到另一条链的头」。注意切换的判断依据是当前指针为空，而不是「当前是尾节点」——正因为多经过了这个null状态，不相交时两者才能同时落到null上并终止。- 只切换一次：每个指针最多经历一次「换链」，因为第二遍走的路径总长恰好覆盖
x + y + z，走完就相遇或双双为空，不会无限绕。- 返回
a：相交时a是公共节点，不相交时a为null，两种情况同一条返回语句。以 A =
4 → 1 → 8 → 4 → 5、B =5 → 6 → 1 → 8 → 4 → 5走一遍，公共段从节点8开始，x = 2、y = 3、z = 3。两个指针依次访问的节点是：
a:4, 1, 8, 4, 5, null, 5, 6, 1, 8；b:5, 6, 1, 8, 4, 5, null, 4, 1, 8。逐位比较：第 1 步4与5不等，第 2 步1与6不等，第 3 步8与1不等（注意此处a已到公共段但b还没有，所以不会误判），第 4 步4与8不等，第 5 步5与4不等，第 6 步null与5不等，第 7 步5与null不等，第 8 步6与4不等，第 9 步1与1——这两个1分别属于 B 的第三个节点和 A 的第二个节点，是不同对象，引用比较为假，所以不会误判；第 10 步两者都到节点8，是同一个对象，循环退出，返回节点8，正确。再看不相交用例 A =
2 → 6、B =1：a走2, 6, null, 1, null，b走1, null, 2, 6, null。第 3 步null与2不等，第 4 步1与6不等，第 5 步两者同时为null，a != b为假，退出并返回null，无需任何特判。
代码实现
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
// 走到尽头就切到另一条链，保证两者总路程都是 x + y + z。
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a, b := headA, headB
for a != b {
// 走到尽头就切到另一条链，保证两者总路程都是 x + y + z。
if a != nil {
a = a.Next
} else {
a = headB
}
if b != nil {
b = b.Next
} else {
b = headA
}
}
return a
}
复杂度分析
- 时间复杂度：$O(m+n)$，
m、n分别是两条链的长度。每个指针最多把两条链各走一遍，总步数上界是m + n + 1，循环体内只有一次判空和一次赋值。- 空间复杂度：$O(1)$，只有
a、b两个引用，没有哈希集合也没有递归栈；正是靠「换链」这个技巧才省掉了记录长度或历史节点的额外结构。
关键点总结
- 单节点只有一个
next，决定了相交链表必然是 Y 字形而非 X 字形，公共段一旦开始就到底——这是所有推理的地基，面试时值得先说这一句。- 「补齐长度差」不必真的去算差值，让两个指针各走一遍两条链，总路程自动相等，这是把显式计算换成对称构造的典型技巧。
- 循环出口同时承担「相遇」和「都为空」两种语义，靠的是让指针经过
null状态再换链；换链条件写「当前为空」而不是「下一个为空」，正是为了保留这个状态。- 相交必须按引用判断，值相等只是巧合，这类题一旦写成比值就会在含重复值的用例上翻车。
- 面试视角：先讲哈希集合法证明思路可行，再讲「对齐长度」法说明 $O(1)$ 空间可达，最后给出换链写法并解释总路程相等与不相交自然终止。能主动说出「不相交时两者同时为
null，所以不需要特判」通常是加分点。
易错点总结
- 换链条件写成
a.next == null ? headB : a.next：不相交时两个指针永远跳过null状态，A =2 → 6、B =1会在两条链之间无限循环，直接超时。- 用
a.val == b.val作循环条件：A =1 → 9、B =1 → 2 → 9且不相交时，第一步两个1就被判为公共节点，返回错误结果。- 只让一个指针换链：例如只写
a的切换而b走完就停，两者路程不再相等，A =4 → 1 → 8、B =5 → 6 → 1 → 8会错过节点8。- 循环内先取
next再判空：写成a = a.next; if (a == null) a = headB;，会在a为空时对空引用取next，直接空指针异常。- 切换时写成
a = headA（切回自己）：指针在本链上无限打转，任何不相交用例都会死循环。- 返回
headA或b之外的变量：循环退出时a与b已相等，返回b也对，但返回headA会把 A 的头当成公共节点，4 → 1 → 8与5 → 6 → 1 → 8会错误返回4。- 提前特判「长度相同就直接逐位比较」：两条链长度相同但不相交时（如
1 → 2与3 → 4），逐位比较不会出错但会退化成另一套逻辑，白白增加分支，且长度相同却在中途相交的情形容易漏判。- 为了对齐长度而修改链表（如反转或接尾成环）：题目要求保持原结构，判题会在返回后校验链表，修改会导致结果被判错。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 160. 相交链表 | 简单 | 与本题同题，可直接套用换链写法 |
| 面试题 02.07. 链表相交 | 简单 | 与本题同题，可直接套用 |
| 142. 环形链表 II | 中等 | 同样求「首个公共节点」，但公共点由环产生，需靠速度差与推导定位 |
| 141. 环形链表 | 简单 | 只判断是否存在自交，不必返回具体节点 |
| 21. 合并两个有序链表 | 简单 | 同样是两条链齐头并进，但推进依据是值的大小而非路程对齐 |
| 86. 分隔链表 | 中等 | 用两条链分别收集节点再拼接，练的是同一套「多指针管多条链」手感 |