企业官网建设流程全解析

LeetCode热题100里的相交链表，我当年刷的时候第一反应就是“这不就双重循环找相同节点吗”，结果看到题目最后那句“尽量满足O(n)时间、O(1)空间”才反应过来，这题没那么简单。后来它成了我面试时特别喜欢拿出来讲的题，因为它考察的点非常集中：你理不理解链表里“节点”的本质，你会不会把“值相等”和“对象相同”混为一谈，你能不能从一个看似绕圈的双指针方案里，看出它本质上是在做路程补偿。

这篇文章我会从最好上手的哈希解法讲起，再重点拆解双指针为什么一定能相遇、没有交点时又发生了什么，最后补几个面试官经常追问的变体。不管你是刚开始刷链表，还是已经准备面试冲刺，照着下面的思路走一遍，再回头看这题应该会觉得通透很多。

1. 换个角度读题：相交链表究竟在找什么

1.1 相交不是值相等，而是对象相同

先看链表节点的基本定义。单链表节点只有两个字段：val保存当前节点的值，next指向下一个节点。在 Java 里ListNode是一个对象，在 Python 里也是一个对象。两个节点就算val完全一样，只要是分别创建出来的，它们在内存里就不是同一个东西。

我见过不少初学者，一看到两个链表里都有数值为 1 的节点，就恨不得把第一个出现的 1 当成交点。这是整道题最大的坑。题目要返回的，是两条链表从某个节点开始、后续所有节点完全共用的那个起始节点。换句话说，你返回的必须是一个内存地址相同的对象，而不是数值碰巧相等的节点。

理解到这一层，代码里的比较方式就自然对了。Java 里判断两个节点是否相同，应该用pa == pb，比较的是引用地址，而不是pa.val == pb.val。Python 里应该用pa is pb，而不是pa == pb。默认情况下，ListNode 的相等和哈希都基于对象身份，所以哈希集合也可以直接存节点对象。

1.2 从题目约束反推考官的意图

原题最后有一行小字：时间复杂度最好控制在 O(n)，空间复杂度尽量控制在 O(1)。几乎是在明示：别用双重循环硬莽，也别满足于哈希表解法。

做题前先看约束是个好习惯。这道题两条链表的长度 m 和 n 都可能很大，如果双重循环逐个比，复杂度是 O(m*n)，在长用例上基本会超时。于是问题就变成了：能不能不用哈希表，不开额外数组，只用两个指针在线性时间内找到交点？

这种“空间受限 + 线性时间”的组合，指向的就是指针技巧。而链表里最高频的指针技巧无非是快慢指针、双指针错位移动这类东西。看到这个约束，基本就能猜出最优解的大方向了。

1.3 先画一张标准相交结构

刷链表题，画图永远比背答案管用。假设两条链表这样相交：

A: 4 -> 1 -> 8 -> 4 -> 5 ↑ B: 5 -> 0 -> 1 —┘

这条竖线表示：A 链表里 4、1 之后是 8，B 链表里 5、0、1 之后也是同一个 8，从 8 开始后面的节点完全共享。注意，这里 A 的 1 和 B 的 1，虽然值一样，但斌不是同一个节点。如果题目示例里故意把两个 1 标识成不同的对象，那就是在考验你会不会被值骗过去。

在刷题平台上，共享节点是通过构造时引用同一个对象实现的。平台先创建好公共链表段，然后分别把两个头节点接到公共段上。所以你只看题目给的数组形式看不出来哪些节点是共享的，只有运行到引用相等那一刻才会真相大白。这也是这类题特别强调“节点对象”而不是“节点值”的原因。

2. 保底解法：哈希集合怎么写才不扣分

2.1 暴力双重循环：能说思路，但别指望它过

面试现场如果一时没思路，最稳妥的开局是这么说：“我先把 A 的每个节点到 B 里从头到尾找一遍，判断有没有引用相同的节点。”这个思路本身没有任何错，时间复杂度是 O(m*n)，空间复杂度 O(1)，正确性也完全没问题。

但它过不了大用例。链表题的数据规模经常能把你卡到超时，所以暴力法更适合作为口头分析的起点，不适合当作最终提交的代码。紧接着补一句“我可以用哈希表把时间降到 O(m+n)”，面试官基本就会让你继续。

2.2 哈希集合解法的完整实现

思路一句话：先把其中一条链表的所有节点引用放进哈希集合，再遍历另一条链表，第一个在集合中出现的节点就是交点。

前面已经解释过，只要节点的 equals 和 hashCode 逻辑基于对象身份，这个方案就能精确定位“同一个对象”。Java 里的 ListNode 默认就是这样。Python 里默认也是这样，前提是你没有在类里重写奇怪的方法。

给一份 Java 写法：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> visited = new HashSet<>(); ListNode p = headA; while (p != null) { visited.add(p); p = p.next; } p = headB; while (p != null) { if (visited.contains(p)) { return p; } p = p.next; } return null; }

Python 版本同样简单，注意用is或者直接让集合存对象：

def getIntersectionNode(self, headA, headB): seen = set() p = headA while p: seen.add(p) p = p.next p = headB while p: if p in seen: return p p = p.next return None

这里有个细节值得说。Python 的 set 依赖__hash__和__eq__两个魔法方法。LeetCode 环境里定义的 ListNode 默认按对象身份生成哈希和比较，所以p in seen判断的是对象身份，能正常工作。但如果你在自己的调试代码里给 ListNode 重写了__eq__，比如改成比较 val，那么集合的行为就会彻底改变，很容易踩坑。刷题时尽量避免给链表节点类加自定义相等逻辑。

2.3 哈希解法的复杂度与适用场景

时间上，两个链表各被完整遍历一次，一共 O(m+n)，这一点已经达标。空间上，最坏情况是把第一条链表的所有节点都存进集合，额外 O(m)。

哈希解法的优点是逻辑直白、不容易写错，作为保底方案完全没有问题。但面试官通常还会追问一句：“你能不能不开哈希表？”这说明它还不是最优解，因为额外空间不是 O(1)。这个时候再引出双指针，让面试官看到你不止会背答案，还理解怎么一步步压缩空间。

3. 双指针的相遇机制：用路程公式拆穿它的底牌

3.1 双指针的行为描述

双指针解法代码量很少，但第一次看到的人多半会愣一下：两个指针明明各自在不同链表上，怎么绕着绕着就相遇了？

具体行为是这样：

• 指针 pa 从 headA 出发，每次移动一步；
• 指针 pb 从 headB 出发，每次移动一步；
• 当 pa 走到链表末尾也就是 null，就把 pa 重新指向 headB；
• 当 pb 走到链表末尾也就是 null，就把 pb 重新指向 headA；
• 循环继续，直到 pa 和 pb 指向同一个节点。

如果两条链表有交点，这个“同一个节点”就是第一个交点；如果没有交点，pa 和 pb 最终会同时变成 null，循环退出，返回 null。

它最妙的地方在于：两个指针从头到尾都没有显式地计算长度、比较长短、交换链表，只是各自走完自己的路之后换一条路继续走，最终却在同一时刻站在了同一地点。

3.2 用路程公式证明为什么一定会相遇

我来解释一下这招为什么有效。设交点前 A 链表独有的长度为 a，B 链表独有的长度为 b，从交点到链表末尾的公共部分长度为 c，这个 c 包含交点本身。

两链表的全长分别是 a+c 和 b+c。现在跟踪 pa：

• 它先走 A 链表全程，经过 a+c 个位置到达 null；
• 跳到 headB 后，再走 B 链表交点前的 b 个节点，到达交点。

所以 pa 从出发到交点，总共经过 a+c+b 个位置。

再跟踪 pb：

• 它先走 B 链表全程，经过 b+c 个位置到达 null；
• 跳到 headA 后，再走 A 链表交点前的 a 个节点，到达交点。

所以 pb 从出发到交点，总共经过 b+c+a 个位置。

两个式子恰好相等。因此只要两条链表确实相交，两个指针就必然会在同一时刻出现在交点位置。这个“走到 null 就换对方链表”的操作，本质上是在补偿两条链表交点前长度的差异。谁短，谁就先走完、先切换，然后去补对方独有段的长度。

一句话总结：双指针相遇的关键，是让两个指针各自走完“自己全部 + 对方独有部分”，总路程对齐为 a+b+c。

3.3 一个具体例子的完整推演

公式再漂亮，也不如亲手推一遍。我用前面那个示例走一遍。链表 A 是 [4,1,8,4,5]，链表 B 是 [5,0,1,8,4,5]，从值为 8 的节点开始共享。A 独有部分 a=2，即 4 和 1；B 独有部分 b=3，即 5、0、1；公共部分 c=3，即 8、4、5。

下面这张表记录的是“进入循环前” pa 和 pb 分别指向什么节点：

注意看第9轮，pa 和 pb 指向的两个节点值都是 1，但一个是 B 链表里的节点对象，一个是 A 链表里的节点对象，内存地址不同，所以pa != pb。如果代码里傻乎乎写成比较val，这一轮就会误判成相等，直接返回错误节点。这张推演表恰好把值比较的荒谬彻底暴露出来。

第10轮进入循环前，pa 指向 B 的 8，pb 指向 A 的 8，这两个本来就是同一个对象，因为从 8 开始就是共享段。此时循环条件不成立，退出，返回 8。

从轮次上也能看到，前几轮 pa 一直显得比 pb“慢”，因为 A 比 B 短。切换到对方链表之后，pb 去补 A 的独有部分，pa 去补 B 的独有部分，两者步调完全对齐。

3.4 没有交点时，两个指针也不会死等

如果两条链表根本不相交，双指针会不会陷入死循环？不会。设 A 长度为 la，B 长度为 lb。

pa 先走完 A 的全部 la 个节点，到 null，随后跳到 headB，再走 lb 个节点。pb 先走完 B 的全部 lb 个节点，到 null，随后跳到 headA，再走 la 个节点。最终双方都经历 la+lb 个位置的变化，同时停在 null 上。此时pa == pb成立，因为两者都是 null，循环条件pa != pb失效，函数返回 null。

所以无交点情况下，算法仍然在线性时间内正常结束，并且不会误报。顺带一提，正因为这个性质，双指针解法其实不需要额外判断 headA 或 headB 是否为空。不过提前写一行if (headA == null || headB == null) return null;会让边界情况更直观，也不会有副作用。

4. 双指针落地：代码细节与三个最容易翻车的边界

4.1 标准实现（Java 与 Python）

双指针代码本身就特别短，先看 Java：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pa = headA; ListNode pb = headB; while (pa != pb) { pa = (pa == null) ? headB : pa.next; pb = (pb == null) ? headA : pb.next; } return pa; }

Python 版本推荐用is判断对象同一：

def getIntersectionNode(self, headA, headB): if not headA or not headB: return None pa, pb = headA, headB while pa is not pb: pa = headB if pa is None else pa.next pb = headA if pb is None else pb.next return pa

无论 Java 还是 Python，循环体里都只有两条赋值语句。没有长度计算，没有栈，没有哈希表。整个算法的核心就是“走到 null 就换一条链表继续走”。

4.2 两种切换写法，建议用可读性更好的一种

除了三元表达式，也有人会这样写：

while (pa != pb) { if (pa == null) { pa = headB; } else { pa = pa.next; } if (pb == null) { pb = headA; } else { pb = pb.next; } }

两种写法本质完全一样，三元表达式更简洁。我个人的建议是：面试现场写代码，优先用展开后的写法，因为每一行都直白，不容易把“pa 为 null 时切换、非空时走 next”的顺序搞反。刷题时用三元表达式更爽利。核心是理解pa == null ? headB : pa.next的语义：先判断当前节点是否到了末尾，到了就重定位到另一条链表头部，没到就正常向后走一步。

4.3 三个最容易翻车的边界

第一个坑：用pa.next == null判断是否走完。

有人觉得pa == null时再切换，等于多做了一次判断，于是改成pa.next == null时切换。这在某些情况下会出错。指针走到 null 时，它已经没有“下一个节点”的概念了，只有直接比较 pa 本身才能正确检测到链表走完。如果用pa.next == null，pa 会停留在最后一个节点上就切换了，等于提前离开当前链表，破坏“先走完全程再切换”的路程平衡。

第二个坑：在 while 条件里加pa != null && pb != null。

有人会写while (pa != null && pb != null && pa != pb)。这看起来合理，但两条链表长度不同时，短链表先到 null，循环直接退出，后面再无追赶的机会。正确的做法是不要限制pa != null && pb != null，让指针通过切换去补足路程。

第三个坑：比较pa.val == pb.val而不是pa == pb。

我在前面反复强调，这里要再点一次名。题目示例特意设计两个 val 都是 1 但并非同一节点的情形，就是为了淘汰用值比较的写法。链表相交题的输出必须是内存中的同一个对象，而不是数值相等的节点。这一点无论你用哪种解法，哈希还是双指针，都一样。

4.4 复杂度与为什么它能做到 O(1) 空间

时间上，在最坏情况下，pa 会走完 A 的全部再走完 B 的全部，pb 会走完 B 的全部再走完 A 的全部，每个指针最多移动 m+n 次。所以整体时间复杂度是 O(m+n)。

空间上，自始至终只用了两个指针变量，没有额外的集合或栈，空间复杂度 O(1)。这就是题目希望看到的解。

如果面试官追问“能不能用更少的空间，比如一个指针？”要如实回答做不到。线性链表的相交检测，单指针无法同时记住两条链表的相对位置，双指针已经是最小空间需求了。除非允许破坏链表结构或修改节点，否则没有更省的方案。

5. 从这道题往外走：有环、栈解法与面试追问

5.1 当题目条件变成“可能有环”

很多面试官不满足于无环场景，会追问：如果两条链表可能有环，双指针解法还成立吗？

结论是：不成立。双指针的路程公式依赖“每条链表能走到 null 再切换”的终止行为。一旦有环，指针会在环里无限绕圈，pa == null这个切换条件永远触发不了，整个循环变成死循环。

正确的处理思路分三步：

1. 分别对两条链表做环检测，用快慢指针。如果一条有环、一条无环，那它们不可能相交，因为相交后公共部分会把环共享给另一条。
2. 如果两条都无环，回到本题的双指针解法。
3. 如果两条都有环，先判断两个环入口是否相同。入口相同，说明交点在入环之前或就在入口，可以退化成无环场景处理；入口不同，则从一个环入口出发在环内走一圈，如果能到达另一个环入口，说明两条链表共享同一个环，交点就在环内。

这个答案链条比较长，但如果面试官真的问到，你能把这个思路列出来，留下的印象比只会背双指针的人深很多。

5.2 如果只问“是否相交”，有个更短的方案

有时候面试题会简化成只判断两条链表是否相交，不要求返回交点。此时有一个非常巧妙的做法：

分别遍历两条链表，记录各自的尾节点。如果两个尾节点是同一个对象，说明它们一定相交；否则不相交。

原理很简单：两条链表相交的拓扑结构决定了从交点之后的所有节点都共享，所以两条链表的最后一个节点必然相同。这个做法时间复杂度 O(m+n)，空间 O(1)，代码量比双指针还少。不过它只能回答 yes or no，不能回答交点是谁。

5.3 从尾部视角切入：两个栈的做法

还有一个容易忽略的思路：既然公共段一定在尾部，可以用两个栈把两条链表从后往前弹出来比对。

把 A 的所有节点依次压栈，再把 B 的所有节点依次压栈。然后同时弹出栈顶，只要两个节点相同，就继续弹出并把答案记为当前节点；一旦遇到不同节点就停止。最后一次弹出来的相同节点，就是交点。

看代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Deque<ListNode> stackA = new ArrayDeque<>(); Deque<ListNode> stackB = new ArrayDeque<>(); for (ListNode p = headA; p != null; p = p.next) { stackA.push(p); } for (ListNode p = headB; p != null; p = p.next) { stackB.push(p); } ListNode ans = null; while (!stackA.isEmpty() && !stackB.isEmpty() && stackA.peek() == stackB.peek()) { ans = stackA.pop(); stackB.pop(); } return ans; }

这个做法直观，但空间 O(m+n)。它提示了一个通用技巧：很多链表问题在正向不好处理时，可以尝试用栈或递归实现反向遍历。面试时如果候选人能给出这种解法，至少说明他对链表遍历路径的理解比较灵活。

5.4 工程视角：链表相交模型能干什么

也许你会觉得这种链表题偏理论，但“两条链从某个位置开始共享后续节点”这个结构，在真实系统里确实会出现。比如某些内存分配器的空闲块链表、版本管理工具里的提交记录链、公共依赖图里的节点复用。当某个公共对象被两条链路同时引用时，你就可能遇到判断两条链路是否汇合的需求。

做题的意义也在于训练这种建模能力。你能从一个链表题里抽出“引用共享”和“相对路程”两个概念，以后遇到更复杂的对象图问题，至少知道该往指针补偿、环检测那个方向想。

我在实际刷这道题的时候，第一遍用哈希集合很快写完了。后来强迫自己不看答案推导双指针，推了三遍才完全对上每一步。真正彻底记住，是从手动画了那张 10 轮推演表开始的。链表题最怕的是不看图直接莽代码，多花两分钟把节点引用和共享段画清楚，很多看起来绕的逻辑一下子就顺了。

最后分享一个小习惯：每次做完链表题，我都会在代码旁边标一句“这个解法依赖的核心不变量是什么”。相交链表的核心不变量，就是两个指针的总路程最终对齐。把这句话写进注释里，会比背任何模板都有用。