相交链表这道题我在LeetCode上刷到过也在面试中被人问过。它看起来平平无奇——给你两个链表找出它们相交的起始节点——但真到写代码的时候不少人会卡住。还有更多人虽然能写出那个经典的双指针解法但你要是追问一句为什么两个指针走完一条链表再走另一条就一定能碰上他又说不清楚了。这篇文章我打算把这题的来龙去脉完整拆一遍从最简单的暴力思路讲到最优解再讲清楚那些网上资料通常一笔带过的原理细节。无论你是刚接触链表的新手还是准备面试想把这题聊透的选手这篇都应该对你有帮助。1. 先从题目本身说起相交到底在说什么很多人在相交链表这题上犯的第一个错不是代码写错而是没理解题目里相交的精确含义。题目给的描述大致是编写一个程序找到两个单链表相交的起始节点。下面通常会跟一张图画着两个链表在一个节点之后合并成同一条链表整体呈Y字形。注意这个形状——是Y不是X。为什么不会是X因为这是单链表每个节点只有一个next指针。如果一个链表真的呈X形意味着某个节点有两个不同的后继这在单链表结构里根本不可能存在。所以两个链表一旦相交从交点开始后面所有节点都是共用的一直到链表结束。我在学习的时候吃过一个亏一开始用节点的值相等来判断相交跑测试样例发现错得离谱。链表节点A的值是1节点B的值也是1但它们是完全独立的两个节点。判断相交要比较的是节点的引用——也就是节点在内存中的地址而不是节点存储的值。只不过在刷题平台上可视化测试用例会直接把相交部分共用而我们写代码时要用a is b或者C里的a b指针相等去判断才会得到正确结果。这题的进阶要求也值得一提你能否在O(n)时间复杂度、O(1)空间复杂度内解决也就是说只能遍历有限的次数并且不能用额外的哈希表、数组或者集合来存节点。这个要求直接堵死了把所有节点存下来再逐个比较这条简单路线逼迫你去找更巧妙的办法。从面试的角度看这道题测的东西很精准链表的基本操作、复杂度的分析能力以及最重要的一点——能不能从两个链表的几何关系里看出隐藏的对齐思路。它不涉及复杂的算法范式没有动态规划没有贪心策略考察的全是基本功和观察力。这也是为什么很多面试官喜欢用它来做热身题——你觉得简单但简单题最容易暴露你有没有真正理解数据结构。2. 我先用最笨的办法跑了一遍暴力解法的价值我第一次做这题思路非常直接拿链表A的每一个节点去链表B里从头到尾找一遍看有没有哪个节点和它引用相同。翻译成代码def getIntersectionNode(headA, headB): while headA: p headB while p: if headA is p: return headA p p.next headA headA.next return None这个解法正确吗正确。能过测试吗能如果链表不长的话。但它有两个很大的问题。第一是时间复杂度。假设链表A有m个节点链表B有n个节点外层循环要跑m次内层循环每次要跑n次整体是O(m*n)。一旦两个链表长度都到几千或几万这个解法会慢到让人怀疑是不是死循环了。第二是它完全浪费了一个重要信息两个链表相交之后的所有节点是完全相同的。也就是说如果我们能确定两个链表从某个位置开始重合那么交点之前的部分长度差是可以算出来的。暴力解法根本没有利用这个几何性质它只是盲目地全量查找。不过我得说句公道话暴力解法并不是毫无价值。我在很多实战场合都发现拿到一道题先写一个朴素但正确的解法能帮你确认自己对题意的理解是对的。尤其是链表这种数据结构边界条件多空链表、只有一个节点、头节点就是交点等等一个朴素解法可以快速帮你把测试用例跑通再来优化的时候至少你有一个正确版本作为参照不至于在优化过程中把逻辑改错。暴力解法还有一个作用就是让你真切体会到优化的必要性。当你的解法被判超时你再去学双指针解法会有一种原来如此的顿悟感。如果你一上来直接背最优解代码很容易陷入会写但不懂的状态面试的时候最怕这种情况——面试官多问一句为什么你就露馅了。顺着暴力解法往下想很自然会想到一个优化如果先把一个链表的所有节点存进哈希表再遍历另一个链表去哈希表里查不是省掉了一层循环吗def getIntersectionNode(headA, headB): seen set() while headA: seen.add(headA) headA headA.next while headB: if headB in seen: return headB headB headB.next return None哈希表解法的时间复杂度可以降到O(mn)空间复杂度则是O(m)或O(n)取决于你把哪个链表装进集合。这个解法在LeetCode上完全能通过而且代码写起来几乎不可能出错。但题目要求的O(1)空间复杂度它满足不了。如果你在面试中直接甩出这个解法很容易被追问一句能不能不用额外空间——这其实就是引导你往双指针方向想。有意思的是哈希表解法虽然不符合进阶要求但你真去面试的时候先说出哈希表解法、再沿着如何去掉这个set的思路推出双指针解法会让面试官觉得你的思路是从约束条件里自然生长出来的而不是背了模板。所以我建议你两个解法都掌握理解它们各自的取舍。3. 双指针解法的两个理解视角对不齐的长度该怎么处理现在来到重头戏双指针解法。网上流传的版本长这样def getIntersectionNode(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 pA非常短短到让人怀疑这题是不是就这么简单。但如果你只是想把这行代码背下来下次遇到可能还是不会做。我接下来用两个不同的视角来解释这个解法都是我实际复盘时用过的思路你可以挑一个更好接受的理解方式。3.1 视角一先算长度差再同步前进两个链表相交的特征是什么是相交部分完全共用。那在相交之前的部分呢两段是彼此独立的。假设链表A在交点之前的长度为a链表B在交点之前的长度为b相交部分的长度为c。注意a和b不一定相等这恰恰是问题的难点——如果a等于b那我们只需要两个指针从两个链表头部同步往前走走一步比一次第一个相等的节点就是交点。可现实往往是a不等于b同步走的话两个指针永远踩在不同的位置上。怎么解决核心思路是让两个指针在距离链表末尾相同距离的位置开始同步走。如果先遍历一遍两个链表把长度分别算出来假设是m和n那么长链表上的指针就要先走 |m-n| 步把长度差抹平之后两个指针再同步前进第一个碰面的节点就是交点。这个思路很直观实现起来也不难def getIntersectionNode(headA, headB): lenA, lenB 0, 0 pA, pB headA, headB while pA: lenA 1 pA pA.next while pB: lenB 1 pB pB.next pA, pB headA, headB if lenA lenB: for _ in range(lenA - lenB): pA pA.next else: for _ in range(lenB - lenA): pB pB.next while pA is not pB: pA pA.next pB pB.next return pA这段代码的正确性很容易验证。它先算长度再对齐然后同步走。为什么这种方法一定有效因为两个指针一旦处在距离链表末尾相同距离的位置上它们之后走过的路径长度完全一致。如果链表相交那么在交点处它们会同时到达如果链表不相交它们会同时走到两个链表的末尾都是None循环结束时pA是None返回None。我用这个思路给一个朋友讲过这道题他的反应是这不就完了吗为什么会有人觉得这题难确实长度差思路不难写起来也顺。那为什么双指针解法更出名因为上述代码需要先遍历两遍链表计算长度总共要跑两趟而双指针解法只需要一趟逻辑上的遍历代码还更短。更重要的是双指针解法里藏着一个极聪明的自动对齐机制理解了它你会觉得这个解法是真的巧妙。3.2 视角二走完自己再走对方本质是路程补偿双指针解法的核心就一句话每个指针都走一条拼接路——完整走完链表A再走链表B另一个指针则完整走完链表B再走链表A。你可能会问这为什么能对齐我来推算一下。指针pA的完整路程是链表A的所有节点数 链表B的所有节点数也就是mn。指针pB的完整路程是链表B的所有节点数 链表A的所有节点数也就是nm。看这两个数字是相等的。路程相等有什么用我们换一个角度来想。在上一篇的长度差思路里我们是人为计算长度差来对齐而在这里两个指针各自走完整条列表的组合路程等于两个人分别跑了完全相同的总距离。更重要的一点是两个指针在各自路程中的相对位置始终存在某种对应关系。我不喜欢用总路程相同来解释因为初看之下你并不知道交点到底在路程的哪个位置。我想分享一个更形象的比喻两个人赛跑其中一个人先跑了一段相当于链表A比链表B长然后让两个人都跑全程m或全程n最终他们会在某一段赛道上同时到达同一个地点——这个地点在最坏情况下是终点None在一般情况下的第一个重叠点就是交点。如果你学过一些概率或者组合可以把这想象成两个不同长度的链各自接上对方的尾巴变成两条等长的链。既然两条新链一样长那么从各自头部出发的两个指针每走一步都处于距离新链末尾相同的距离的位置。而由于两条新链的后半段对应在原链表里相交的部分是完全一样的节点所以在某个节点上两个指针一定会踩到同一个对象。我第一次理解这个解法的时候不是通过数学推导而是真的在纸上画了两个长短不同的链表然后在第二个链表后面接上第一个链表、在第一个链表后面接上第二个链表画完就明白了。你也可以试试这个办法——画图永远比背结论有效。沿着这个思路再看代码还有一个隐藏得很深、但很关键的细节两个指针同时到达None也是一种相遇。如果没有交点pA走完A再走B到最后pB走完B再走A到最后二者都变成None。此时pA is not pB为假循环结束返回pA也就是None。所以这个解法天然就处理了不相交的情况不需要额外写判断。4. 双指针解法代码实现与边界条件别在这些地方翻车代码虽然短但我在实际写的时候发现有两个地方特别容易写错一个是循环条件另一个是空指针的判断方式。先看循环条件。很多版本会写while pA ! pB:这没问题但在Python里需要注意链表节点本身没有定义__eq__方法时比较的就是引用所以pA ! pB本质上也是在比较引用。不过为了语义清晰我建议直接用is not明确告诉读者我们比较的是是否是同一个对象。第二个容易踩的坑是跳转语句的写法。看这段代码pA pA.next if pA else headB pB pB.next if pB else headA这里我用的是if pA而不是if pA.next。为什么因为如果pA已经走到链表末尾pA是None你还去访问pA.next会直接抛出AttributeError: NoneType object has no attribute next。这个错误我至少犯过两次都是因为脑子里想着走完了就跳转那应该是pA.next为空时跳转结果忘了先判断pA本身是否为None。正确理解是当pA是None时说明它已经走完了当前链表该切换到另一个链表了。所以判断条件得是if pA而不是if pA.next。还有一种更直观的写法是先判断再移动while pA is not pB: if pA is None: pA headB else: pA pA.next if pB is None: pB headA else: pB pB.next return pA这种写法和前面的三目运算符版本是完全等价的但读起来更不容易出错。如果你是在面试现场手写代码我建议你用这种拆开写的版本因为面试官更看重你思路是否清晰而不是代码是否足够精简。然后我们来看边界条件的处理。空链表如果headA或headB是None代码会怎么走第一轮循环判断pA is not pB此时一个是None一个是某个节点条件成立进入循环后pA为None则跳转到headB也是NonepB则继续走。最终两个指针中会有一个先耗尽路程变成None另一个也很快变成None循环结束返回None。整个过程不会崩但为了效率你也可以在一开始就加一行提前判断if not headA or not headB: return None这行其实并不是必须的但写上也挺稳妥特别是你在和面试官讲解的时候主动提一句空链表直接返回None会给对方留下考虑周全的印象。两个链表从第一个节点就相交此时headA就是headB第一轮循环条件pA is not pB直接不成立返回headA。代码不出错但如果你在循环里先移动指针再判断就会错过去所以注意循环条件的判断时机。链表中只有一个节点且不相交比如A是[1]B是[2]。pA走完A之后跳到B的开头pB走完B之后跳到A的开头再次经过一轮两个指针同时变成None返回None。这个过程中两个指针永远不会指向同一个非空节点——因为根本没有交点。还有一个我自己做测试时发现的坑如果你用while pA and pB:之类的条件去循环会导致部分相交情况提前退出。最安全的写法就是老老实实按pA is not pB来别自作聪明加其他条件。拿Python写完之后我顺手也用C写了一遍核心逻辑完全一样只是把is not换成了!把None换成了nullptr。如果你面的是C岗位建议把这段也练熟因为C里面指针的用法比Python更贴近内存模型写起来思路会更顺。5. 哈希表解法空间换时间的备选方案与面试话术虽然双指针解法是这道题最优解但我觉得哈希表解法仍然值得好好讲讲。原因有两个第一它是一种非常通用的解法思路链表题的找重复/找交点类问题里经常用到第二面试的时候先讲哈希表再优化到双指针这种从直白到巧妙的推进过程本身就是一种很好的答题策略。哈希表解法的代码前面已经给过了核心就两步把链表A的所有节点放进一个集合然后遍历链表B逐个检查当前节点是否在集合中。第一个在集合中出现的B节点就是交点如果遍历完B都没遇到说明两个链表不相交。它的时间复杂度是O(mn)空间复杂度O(m)如果存A的话。有人会问为什么空间复杂度是O(m)而不是O(mn)因为集合里只存了其中一个链表的所有节点。你要是较真的话也可以说O(m)或者O(n)取决于你存的是哪个通常取较大的那个。这个解法相比双指针的优点是思路直白不易出错特别适合在面试一开始快速给出一个可行方案。你甚至可以主动说明这是用空间换时间不符合O(1)空间的进阶要求那我们能不能不用额外空间呢——这句话就像抛出一块砖头顺着去掉哈希表这个念头就引出了双指针解法。在实际刷题过程中我见过不少新手一上来就追求最优解花半小时憋不出代码最后一看答案发现最优解就五行。我的建议是反过来先写一个必然正确的暴力解法或哈希表解法拿到通过的结果之后再思考怎么优化。这样至少保证了能做出来而能优化是在能做出来的基础上讨论的。面试也一样面试官期待看到的是一种逐步改进的过程而不是你背一段最优解背得行云流水。前面提到过一种错误的比较方式用节点的值去判断相交。在这道题里这种错误比较明显因为测试用例可能有多个值相同的节点导致你的哈希表里存了一堆节点却永远找不到真正的交点。这个概念同样适用于哈希表解法必须把节点对象本身存进集合而不是节点的值。Python里哈希需要一个可哈希的对象链表节点默认的object天然是可哈希的所以可以直接存。如果你用自己的类定义注意别把__hash__给覆盖掉了否则会出现意想不到的行为。最后补充一个关于哈希表解法的真实场景。LeetCode上这道题有一个隐藏的坑如果你在本地IDE跑通了一个正确的解法但直接复制到LeetCode提交可能会因为类名或者方法名不一致而报错。我遇到过几次这种情况结论是刷题平台的模板代码一般定义了ListNode和Solution你只需要在类里实现getIntersectionNode方法即可。哈希表解法也不例外测试时会用两个链表的头节点调用你的方法内部怎么实现平台不关心它只看返回值。6. 做题过程中我需要重点避开的几个坑题目本身不难但看着不难恰恰是容易翻车的地方。我在反复做这题的过程中整理出了一批高频错误每一个都是我或者身边朋友亲自踩过的。我把它们列在这里你们刷题的时候可以对照着自查。第一个坑用而不是is。在Python里两个不同的对象即使内容完全一样也不一定返回True——这取决于这个类有没有实现__eq__。链表节点类在LeetCode的原生定义里通常没有实现__eq__所以和is在大多数情况下行为相同。但你不能依赖这个大多数情况尤其到了别的语言里情况又不一样了。C里指针比较就是用因为两个指针指向同一块内存地址时它们相等。Java里则要小心程序员习惯用比较基本类型但比较对象时比较的是引用是否相等这恰恰是我们想要的可有的同学会条件反射写成.equals()那就错了——.equals()默认比较引用没错但如果你Override过equals就会变成比较内容。我建议你在刷题时明确自己在用什么语言遵循该语言的比较习惯。第二个坑忽略不相交也要返回None。有的解法在写完双指针之后想着万一它们不相交就会死循环而加了很多奇怪的判断其实没必要。双指针解法自带处理不相交情况的机制——两个指针最终同时变成None。这个机制我在前面已经详细说明过了。如果你在循环里加了额外的计数器、或者用while pA and pB之类的条件反而可能出错。第三个坑尝试修改链表的指向来标记路径。我见过有人提出这样的思路先遍历链表A把每个节点的next指向自身或者指向一个特殊节点然后再遍历B遇到标记过的节点就是交点。这个思路在部分题目里可以用但在这题里有两个问题一是空间复杂度可能不达标二是修改了链表结构可能破坏后面的测试用例。题目只要求返回相交节点并没有允许你修改链表。面试的时候如果你提出这个思路面试官可能会顺着问那如果要求不修改链表呢你要是答不上来反而减分。第四个坑假定两个链表一样长。我见过不少初学者一看到这题就写while headA and headB: if headA is headB: return headA headA headA.next headB headB.next这个代码在两个链表长度相同时是对的但长度一不等就漏掉交点。原因是两个指针没能对齐。这恰好就是双指针解法要解决的核心问题。如果你写出来这个版本一定要意识到长度可能不同这个前提否则测试用例会给你狠狠上一课。第五个坑不考虑空链表。前面说过双指针代码对空链表也能正常工作但你可以加上提前判断来提升可读性。哈希表解法里如果headA本身是Nonewhile headB:循环可能根本不会执行然后你返回None——也是对的。所以这类边界条件更多是锦上添花而不是救命稻草。但我还是建议你在做题时主动想一想空链表的情况因为面试官真的会问。这些坑归纳起来其实反映了一个共性链表题目里指针是你的核心武器而空值是最常见的敌人。任何一次next操作之前都值得想一想当前这个节点是不是已经是None。一次is not比较之前想想它是不是永远为True。凡是能让代码更防御性的写法面试时都可以主动加上。7. 从相交链表延伸到一类问题链表题里的相遇套路做题有个习惯我坚持了很久一道题做完之后试着把它和以前做过的题建立联系。相交链表这道题看起来独立实际上它和另外几道经典链表题共享着同一个解题内核——两个指针在链表上移动直到满足某个条件。第一类相关题是环形链表。给你一个链表判断有没有环。经典解法是快慢指针快指针每次走两步慢指针每次走一步如果链表有环两者必定在环内相遇如果没有环快指针会先到达None。这个题和相交链表的双指针解法有什么关系表面上没直接关系但如果你深入思考一下它们都在利用路程差或周期性来构造必然会发生的事件——一个有环则必相遇一个相交则必相遇。做多了你会发现链表题的很多精妙解法都建立在任何两个指针在满足某些条件后一定会碰面的洞见上。第二类相关题是找环形链表的入口。LeetCode上有一道题要求在O(1)空间下找到环的入口节点。解法先是用快慢指针找到相遇点然后再用两个指针从头开始走最后在入口处相遇。这个解法里也藏着一个复杂的数学推导需要你理解两个指针在环内相遇时已经走过的路程之间存在某种倍数关系。相比之下相交链表的核心要简单得多——两个指针走的总路程相等然后就自然对齐了。第三类相关题是合并两个有序链表。这个题看起来和相交没什么关系但我常拿来和相交链表做对比合并两个有序链表需要同时遍历两个链表比较当前节点值的大小然后选择更小的那个节点接到结果链上。它和相交链表有一个共同的考点当两个链表长度不一致时你需要小心处理其中一个链表已经走完但另一个还没走完的情况。这种非对称遍历的节奏感做多了以后会觉得特别熟悉。我在这里把这些题串起来是想表达一个观点刷题不能只刷怎么做还要关注为什么这么做。相交链表的最优解表面上是走完A走B走完B走A的口诀实质上是对路程补偿概念的一次展示。你要是在面试中能把这个概念讲清楚面试官对你的评价会明显好于只会背代码的人。还有一种更实用的做法每做完一道链表题就自己改编一下。比如把两个链表改成三个链表找交点或者把单链表改成双向链表看看解法会怎么变。这样做的收益不是立竿见影的但长期积累下来你对链表结构的直觉会灵敏很多。我认识的几位算法水平很高的朋友都是用这种改题训练的方式保持状态的。8. 想通之后这道题就真的简单了最后我再多聊一点个人感受算是我刷了几百道题之后对这些简单题的看法。相交链表这道题我第一次做出正确解法的时候用的是先算长度再对齐的思路。代码写了三十多行跑通了我还挺有成就感。后来看到双指针解法的五行业代码第一反应是什么是这也太短了第二反应是它凭什么能保证相遇我花了不少时间画图、推导、举例子才彻底接受了这个解法。这个过程让我意识到算法题的理解和看懂是两回事。看懂只需要顺着别人的思路走一遍理解则需要你能够在没有提示的情况下自己推到这个解法。所以我建议你不管用什么方式学习这道题最后都停下来做一件小事不看任何资料自己独立推导一遍双指针解法相遇的证明。写不出来也没关系卡住了再看看完再继续推。这个过程重复两三遍这道题在你心里就真正长住了。还有一个小技巧可以分享给你。面试的时候如果被问到这道题你可以在讲完双指针解法之后主动提一句如果不相交两个指针最终会同时到达链表的末尾null所以循环自然结束。这句话听起来像在补充边界条件实际上是在向面试官展示你不仅知道解法还理解了解法为什么会收敛。我见过不少候选人能在白板上默写出双指针代码但一被问如果它们没有交点会发生什么就卡壳。你要是能轻松回答这个问题这轮的印象分会高不少。如果你想把这道题纳入复习体系我建议把它和环形链表、合并两个有序链表放到同一天做。三个题一起做你会发现它们之间有一条隐隐相连的线都是链表上的指针运动问题都在考你怎么处理遍历完一条链去另一条的状态切换。把这些题目放在一起嚼透比单独刷十道不相关的题更有价值。我自己每次做链表题都会提醒自己一句话链表题的难点往往不在于你懂多少数据结构和算法而在于你能不能把一个朴素的想法通过巧妙的指针操作变成高效代码。相交链表这道题就是这种思维转变最好的入门教材之一。