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 之后是 8B 链表里 5、0、1 之后也是同一个 8从 8 开始后面的节点完全共享。注意这里 A 的 1 和 B 的 1虽然值一样但斌不是同一个节点。如果题目示例里故意把两个 1 标识成不同的对象那就是在考验你会不会被值骗过去。在刷题平台上共享节点是通过构造时引用同一个对象实现的。平台先创建好公共链表段然后分别把两个头节点接到公共段上。所以你只看题目给的数组形式看不出来哪些节点是共享的只有运行到引用相等那一刻才会真相大白。这也是这类题特别强调“节点对象”而不是“节点值”的原因。2. 保底解法哈希集合怎么写才不扣分2.1 暴力双重循环能说思路但别指望它过面试现场如果一时没思路最稳妥的开局是这么说“我先把 A 的每个节点到 B 里从头到尾找一遍判断有没有引用相同的节点。”这个思路本身没有任何错时间复杂度是 O(m*n)空间复杂度 O(1)正确性也完全没问题。但它过不了大用例。链表题的数据规模经常能把你卡到超时所以暴力法更适合作为口头分析的起点不适合当作最终提交的代码。紧接着补一句“我可以用哈希表把时间降到 O(mn)”面试官基本就会让你继续。2.2 哈希集合解法的完整实现思路一句话先把其中一条链表的所有节点引用放进哈希集合再遍历另一条链表第一个在集合中出现的节点就是交点。前面已经解释过只要节点的 equals 和 hashCode 逻辑基于对象身份这个方案就能精确定位“同一个对象”。Java 里的 ListNode 默认就是这样。Python 里默认也是这样前提是你没有在类里重写奇怪的方法。给一份 Java 写法public ListNode getIntersectionNode(ListNode headA, ListNode headB) { SetListNode 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(mn)这一点已经达标。空间上最坏情况是把第一条链表的所有节点都存进集合额外 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 链表独有的长度为 aB 链表独有的长度为 b从交点到链表末尾的公共部分长度为 c这个 c 包含交点本身。两链表的全长分别是 ac 和 bc。现在跟踪 pa它先走 A 链表全程经过 ac 个位置到达 null跳到 headB 后再走 B 链表交点前的 b 个节点到达交点。所以 pa 从出发到交点总共经过 acb 个位置。再跟踪 pb它先走 B 链表全程经过 bc 个位置到达 null跳到 headA 后再走 A 链表交点前的 a 个节点到达交点。所以 pb 从出发到交点总共经过 bca 个位置。两个式子恰好相等。因此只要两条链表确实相交两个指针就必然会在同一时刻出现在交点位置。这个“走到 null 就换对方链表”的操作本质上是在补偿两条链表交点前长度的差异。谁短谁就先走完、先切换然后去补对方独有段的长度。一句话总结双指针相遇的关键是让两个指针各自走完“自己全部 对方独有部分”总路程对齐为 abc。3.3 一个具体例子的完整推演公式再漂亮也不如亲手推一遍。我用前面那个示例走一遍。链表 A 是 [4,1,8,4,5]链表 B 是 [5,0,1,8,4,5]从值为 8 的节点开始共享。A 独有部分 a2即 4 和 1B 独有部分 b3即 5、0、1公共部分 c3即 8、4、5。下面这张表记录的是“进入循环前” pa 和 pb 分别指向什么节点循环轮次pa 指向pb 指向是否相等第1轮进入前A 的 4B 的 5否第2轮进入前A 的 1B 的 0否第3轮进入前A 的 8B 的 1(B)否第4轮进入前A 的 4B 的 8否第5轮进入前A 的 5B 的 4否第6轮进入前nullB 的 5否第7轮进入前B 的 5null否第8轮进入前B 的 0A 的 4否第9轮进入前B 的 1(B)A 的 1(A)否第10轮进入前B 的 8A 的 8是返回 8注意看第9轮pa 和 pb 指向的两个节点值都是 1但一个是 B 链表里的节点对象一个是 A 链表里的节点对象内存地址不同所以pa ! pb。如果代码里傻乎乎写成比较val这一轮就会误判成相等直接返回错误节点。这张推演表恰好把值比较的荒谬彻底暴露出来。第10轮进入循环前pa 指向 B 的 8pb 指向 A 的 8这两个本来就是同一个对象因为从 8 开始就是共享段。此时循环条件不成立退出返回 8。从轮次上也能看到前几轮 pa 一直显得比 pb“慢”因为 A 比 B 短。切换到对方链表之后pb 去补 A 的独有部分pa 去补 B 的独有部分两者步调完全对齐。3.4 没有交点时两个指针也不会死等如果两条链表根本不相交双指针会不会陷入死循环不会。设 A 长度为 laB 长度为 lb。pa 先走完 A 的全部 la 个节点到 null随后跳到 headB再走 lb 个节点。pb 先走完 B 的全部 lb 个节点到 null随后跳到 headA再走 la 个节点。最终双方都经历 lalb 个位置的变化同时停在 null 上。此时pa pb成立因为两者都是 null循环条件pa ! pb失效函数返回 null。所以无交点情况下算法仍然在线性时间内正常结束并且不会误报。顺带一提正因为这个性质双指针解法其实不需要额外判断 headA 或 headB 是否为空。不过提前写一行if (headA null || headB null) return null;会让边界情况更直观也不会有副作用。4. 双指针落地代码细节与三个最容易翻车的边界4.1 标准实现Java 与 Python双指针代码本身就特别短先看 Javapublic 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 nullpa 会停留在最后一个节点上就切换了等于提前离开当前链表破坏“先走完全程再切换”的路程平衡。第二个坑在 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 的全部每个指针最多移动 mn 次。所以整体时间复杂度是 O(mn)。空间上自始至终只用了两个指针变量没有额外的集合或栈空间复杂度 O(1)。这就是题目希望看到的解。如果面试官追问“能不能用更少的空间比如一个指针”要如实回答做不到。线性链表的相交检测单指针无法同时记住两条链表的相对位置双指针已经是最小空间需求了。除非允许破坏链表结构或修改节点否则没有更省的方案。5. 从这道题往外走有环、栈解法与面试追问5.1 当题目条件变成“可能有环”很多面试官不满足于无环场景会追问如果两条链表可能有环双指针解法还成立吗结论是不成立。双指针的路程公式依赖“每条链表能走到 null 再切换”的终止行为。一旦有环指针会在环里无限绕圈pa null这个切换条件永远触发不了整个循环变成死循环。正确的处理思路分三步分别对两条链表做环检测用快慢指针。如果一条有环、一条无环那它们不可能相交因为相交后公共部分会把环共享给另一条。如果两条都无环回到本题的双指针解法。如果两条都有环先判断两个环入口是否相同。入口相同说明交点在入环之前或就在入口可以退化成无环场景处理入口不同则从一个环入口出发在环内走一圈如果能到达另一个环入口说明两条链表共享同一个环交点就在环内。这个答案链条比较长但如果面试官真的问到你能把这个思路列出来留下的印象比只会背双指针的人深很多。5.2 如果只问“是否相交”有个更短的方案有时候面试题会简化成只判断两条链表是否相交不要求返回交点。此时有一个非常巧妙的做法分别遍历两条链表记录各自的尾节点。如果两个尾节点是同一个对象说明它们一定相交否则不相交。原理很简单两条链表相交的拓扑结构决定了从交点之后的所有节点都共享所以两条链表的最后一个节点必然相同。这个做法时间复杂度 O(mn)空间 O(1)代码量比双指针还少。不过它只能回答 yes or no不能回答交点是谁。5.3 从尾部视角切入两个栈的做法还有一个容易忽略的思路既然公共段一定在尾部可以用两个栈把两条链表从后往前弹出来比对。把 A 的所有节点依次压栈再把 B 的所有节点依次压栈。然后同时弹出栈顶只要两个节点相同就继续弹出并把答案记为当前节点一旦遇到不同节点就停止。最后一次弹出来的相同节点就是交点。看代码public ListNode getIntersectionNode(ListNode headA, ListNode headB) { DequeListNode stackA new ArrayDeque(); DequeListNode 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(mn)。它提示了一个通用技巧很多链表问题在正向不好处理时可以尝试用栈或递归实现反向遍历。面试时如果候选人能给出这种解法至少说明他对链表遍历路径的理解比较灵活。5.4 工程视角链表相交模型能干什么也许你会觉得这种链表题偏理论但“两条链从某个位置开始共享后续节点”这个结构在真实系统里确实会出现。比如某些内存分配器的空闲块链表、版本管理工具里的提交记录链、公共依赖图里的节点复用。当某个公共对象被两条链路同时引用时你就可能遇到判断两条链路是否汇合的需求。做题的意义也在于训练这种建模能力。你能从一个链表题里抽出“引用共享”和“相对路程”两个概念以后遇到更复杂的对象图问题至少知道该往指针补偿、环检测那个方向想。我在实际刷这道题的时候第一遍用哈希集合很快写完了。后来强迫自己不看答案推导双指针推了三遍才完全对上每一步。真正彻底记住是从手动画了那张 10 轮推演表开始的。链表题最怕的是不看图直接莽代码多花两分钟把节点引用和共享段画清楚很多看起来绕的逻辑一下子就顺了。最后分享一个小习惯每次做完链表题我都会在代码旁边标一句“这个解法依赖的核心不变量是什么”。相交链表的核心不变量就是两个指针的总路程最终对齐。把这句话写进注释里会比背任何模板都有用。