1. 先搞清楚“相交链表”到底在问什么1.1 链表相交不等于两条线交叉两链表相交这六个字看起来简单却是很多人在面试现场翻车的高频题。我见过不止一个候选人代码写出来了被追问一句“为什么双指针最后一定会相遇”就卡住也见过有人张口就是哈希表被要求改成O(1)空间之后直接愣住。这道题之所以经典不是因为它难而是因为它同时考了三样东西对链表内存模型的理解、空间复杂度的优化意识以及把直觉结论转化成严谨表达的能力。很多初学者会下意识把“链表相交”想象成两条线在路上交叉像十字路口那样。这是第一个必须纠正的直觉。单链表里每个节点只有一个next指针它不可能同时指向两条不同的路。所以一旦两条链表真的相交它们后续的所有节点就完全重合整个形状不是“X”而是“Y”。你可以把相交后的那段链表想象成两根吸管汇流进同一根吸管水一旦汇合就不可能再分开。这个模型决定了这道题的一切解法。凡是判断“两条链表是否相交”或者“找出第一个交点”本质上都是在找那个从“各走各的”变成“共用同一段”的临界节点。1.2 一个很少被写进题解的关键推论从“Y型共享”这个模型出发可以直接得到一个非常实用的推论如果两条链表相交那么它们的尾节点一定是同一个节点。这个推论在某些解法里可以当作快速否决条件。比如用双指针求解时先遍历两条链表到底如果发现尾节点不是同一个对象直接返回null不用再进入后续流程。这个判断的成本只是O(mn)的一次扫描却能提前挡掉大量不相交的用例。反向思考一下如果尾节点相同是否必然相交答案是肯定的。因为尾节点意味着后续没有其他节点了两条链表能走到同一个尾节点说明从某个位置开始它们的路径重合了而这个“某个位置”就是交点。所以“尾节点相同”和“两链表相交”在无环链表里是等价的。这一条推论在面试里很常用尤其是面试官问“如果只要求判断是否相交不求交点你能不能用O(1)空间做到”的时候答案就是分别遍历到尾部比较尾节点引用是否相等复杂度O(mn)时间、O(1)空间干净利落。1.3 为什么比较“节点的值”是错的还有一个典型的误区有人会在循环里写if nodeA.val nodeB.val用节点的值判断是否相交。这在特定用例下可能碰巧通过但逻辑上是站不住脚的。举个最直接的例子链表A只有一个节点值是1链表B也只有一个节点值是1。两个节点值相等但它们分别是独立创建的对象内存地址不同根本不相交。相交的定义是“存在共享的节点对象”而不是“存在值相同的节点”。在C/C里应该比较指针地址在Java/Python里应该比较对象引用而不是比较节点内部的val字段。很多在线题库给的数据恰好让值相等的节点出现得非常隐蔽等你交换了顺序、插入了不同值代码立刻暴露出错误。这类bug一旦出在面试的白板代码里非常减分因为它在最基础的模型理解上就错了。所以请记住这句话比较对象引用永远不要比较值。哪怕实际链表里所有节点值都不重复也不该依赖这个巧合。2. 解法一哈希集合法——优先级被低估的保底答案2.1 算法流程与时空复杂度哈希集合法可能是这道题里最好写的方案思路就四步从headA出发遍历链表A把每个节点对象加入一个哈希集合。从headB出发遍历链表B在每次移动前检查当前节点是否已经在集合里。如果存在说明这个节点就是两条链表的交点直接返回。如果链表B走完还没有命中返回null。这个算法的时间复杂度是O(m n)其中m和n分别是两条链表的长度。空间复杂度是O(m)因为需要存下链表A的全部节点。如果把A、B的选择反过来空间复杂度可以压到O(min(m, n))。虽然空间上不算最优但在实战中哈希法最大的优点是不容易写错也不需要理解“Y型共享”带来的各种隐含条件。这段代码我贴一下用Python写最直观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 None2.2 为什么很多题解把它放在最后按理说这是最容易被想到的解法可很多教程偏偏把它排在最后一个讲理由是“空间复杂度不满足最优要求”。但我说句实在话面试现场能稳定写出哈希解法已经能拿到基础分了。面试官最怕的不是你用了额外空间而是你在那儿憋了五分钟连一版能跑的代码都交不出来。哈希法的另一个隐藏优势是它的普适性在链表带环的情况下只要在遍历时额外判断“当前节点是否已经访问过”就能避免死循环。而长度对齐法和双指针交换法基础版本在带环链表里会直接陷入死循环需要额外处理。如果你准备面试我的建议是把哈希法作为“保底方案”装进脑子里。千万别小看保底方案它就像考试时你先用代数法解一道几何题过程不够优雅但能得分。之后如果你有时间再补上O(1)空间的解法面试观感反而更好先给出可行解再展现出优化能力这个顺序在面试官视角里非常加分。2.3 哈希法需要注意的细节哈希法本身简单但有个细节值得提醒在C里如果用了unordered_setListNode*默认就是按指针地址哈希逻辑正确但如果有人为了图方便重载了节点的运算符改成按val比较那set的语义就变成了“节点值集合”上面的逻辑直接失效。Java里HashSetListNode存的也是对象引用除非节点类自己重写了equals和hashCode否则按引用比较是对的。Python同理只要ListNode没有实现__eq__和__hash__默认就是基于对象身份的哈希。还有一个小坑有的链表实现里节点类带有data字段和next字段如果data是可变对象且有人改了值集合里的哈希值可能变化导致if cur in seen判断异常。工程上一般不这么干但刷题时遇到过这种自定义结构就要留个心眼。3. 解法二长度对齐法——最接近直觉的O(1)空间解3.1 思路来源把Y型拉直先回到“Y型共享”的图形上。两条链表在交点前长度可能不同交点后却必然完全一样。假设链表A从headA到交点的路段长度为a链表B从headB到交点的路段长度为b交叉后的共享段长度为c那么链表A的总长度是a c链表B的总长度是b c。如果a b问题就变得极其简单两个指针从头同步出发第一次指向同一个节点时那个节点就是交点。但实际中a和b往往不相等于是最简单的想法就是让长的链表先往后挪动|a - b|步使得两个指针同时处于距离交点相同的位置然后一起走。这就是长度对齐法的核心。它的本质不是想象出来的高深技巧而是把“Y”形结构在视觉上强行对齐成“从同一起跑线出发的两条线”再用同步移动去探测共同节点。3.2 代码实现与“先走diff步”的道理用刚才的例子具体说明。假设链表A是1 - 2 - 3 - 7 - 8 - 9链表B是4 - 5 - 7 - 8 - 9。A的长度是6B的长度是5diff 1。先把A的指针往后移动1步指向2然后两个指针同步移动第1步A指针在2B指针在4第2步A指针在3B指针在5第3步A指针在7B指针在7此时两个指针指向同一个节点这个节点就是交点返回它即可。代码写出来也相当直白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 and pb and pa ! pb: pa pa.next pb pb.next return pa这里第一遍遍历两个链表算出长度差第二遍让长链先走。两个指针都走完|a-b|之后它们离交点的剩余距离是相等的再同步走。如果两条链表根本不相交最终两个指针都会变成null循环自然结束返回null。这个逻辑天然处理了无交点的情况不需要额外的标志位。3.3 什么时候推荐先说长度对齐法长度对齐法在三种解法里是“解释起来最不需要数学功底”的一种。面试官问“为什么能这样”你只需要说两条链表的后半段是一模一样的把前半段的长度差消掉之后后半段就是等长赛道同步走到相同节点就是交点。这个解释几乎不需要公式对方一听就懂。我自己给朋友模拟面试时发现候选人能把长度对齐法讲清楚的比例并不高。大家往往记着双指针那个炫酷的交叉走法但问他一句“如果两条链表长度差很大双指针到头来会不会多绕路”就回答不上来。这时候长度对齐法反而能救人因为它的每一步都有明确的几何意义。时间复杂度依然是O(m n)空间复杂度O(1)。从面试考察“优化空间”的角度它已经满足要求了虽然它比双指针交换法多了一次扫描但常数很小实际性能相差无几。4. 解法三双指针同步交换法——最优雅也最需要证明的写法4.1 那个看起来像魔术的写法在众多题解里有一段代码被引用得最多def getIntersectionNode(headA, headB): if not headA or not headB: return None pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA第一次看到这个写法的人大多会觉得莫名其妙两个指针各走各的走到头就跑到另一条链表的头部继续走凭什么最后会停在交点这段代码短到只有七行但要真正把它“讲明白”比写出它难得多。4.2 相遇即交点的数学解释我用最朴素的方式解释。设链表A在交点之前的长度为a链表B在交点之前的长度为b相交之后的共享长度为c。那么链表A的总长是a c链表B的总长是b c。指针pA从headA出发走完链表A用了a c步到达null然后跳到headB继续走指针pB从headB出发走完链表B用了b c步到达null然后跳到headA继续走。现在想一个问题当pA从headB这一端往交点走时它距离交点还有多少步答案是b - c步因为B链从headB到交点的长度就是b不对等一下这里要更仔细一点。B链的总长是b c但交点距离headB是b步不是b - c。我前面定义里b就是交点前长度也就是从headB出发到交点要b步。由于pA跳到了headB它再走到交点需要b步。而pB跳到了headA它再走到交点需要a步。这样两人第二次出发的路程分别是b和a不一定相等。所以不能用“第二次同步出发”来简单解释。真正的关键在于把第一次走完整条链表也计入总路程。pA第一次走完链表A需要a c步到达nullpB第一次走完链表B需要b c步到达null。相交链表中a c和b c未必相等。但注意此时两人都到了null下一步都会跳到对方的链表头部。从这一刻起pA相当于从头开始走链表BpB相当于从头开始走链表A。如果把pA从出发到第二次走到交点的总步数算出来pA第一次走完链表Aa c步跳到链表B从headB走到交点b步总步数a c b同理pB的总步数第一次走完链表Bb c步跳到链表A从headA走到交点a步总步数b c a是不是完全相等是的两边都是a b c。也就是说尽管两人出发后走过的东西不同、经历的顺序不同但走到交点那一瞬间消耗的步数正好相等。两个指针速度一样从同一个时间点出发走的步数相同就必然在同一时刻到达同一个位置——那就是交点。更简单的一句话版本每个人走完自己的链表后再走对方的链表总行程都是两条链表长度之和但交点在其中占的位置刚好让两人在走完全程的过程中同时踩中它。或者说两个人把两条链表“拼接”成了两条等长的赛道A B 与 B A交点在这两条赛道上的位置是对齐的所以同步出发必会相遇。4.3 无交点时为什么不会死循环很多人担心如果两条链表不相交这个循环会不会永远转下去不会。不相交时可以认为交点后的共享长度c 0。pA最终会走完A链再接上B链pB最终会走完B链再接上A链。两条新赛道都是a b这么长。当两人走到各自的终点时也就是连续走完a b步之后两者同时到达null。由于null null循环条件pA ! pB不再成立循环退出返回pA也就是null。所以这段代码天然把“相交”和“不相交”两种情况都覆盖了。这也是它最妙的地方不需要额外的标志位不需要预先判断循环自己在正确的时候停下来。4.4 代码中容易写错的两个细节第一个细节是空判断。有人为了省事不写if not headA or not headB直接把两个指针初始化为headA和headB。当一条链表为空时pA是nullpB指向不为空循环体里pA pA.next if pA else headB会让pA跳回另一条链表的头部表面上看不会崩溃但会让pB多走很多路尤其是在链表很长的情况下白白增加耗时。所以最稳的做法还是开头先判空语义清晰也能避免各种边界组合的意外。第二个细节是循环条件。很多人会写成while pA ! pB and pA and pB意思是想说“两个都不为空时才比较”。这在相交的情况下也许碰巧正确但在不相交的情况下当两个指针最终都走到null时pA and pB为假循环提前退出返回的是pA也就是null看起来也能通过测试。可一旦题目要求返回“第一个交点”这种写法在极端用例下有隐患如果两条链表完全不相交但在循环退出前恰好出现pA为空而pB非空的情况返回值就可能不是null而是空指针之后被跳转到的某个非空节点。测试数据有时候测不出来但逻辑上是错的。最规范的写法就是while pA ! pB让pA pB null作为正常退出条件。5. 边界陷阱与面试官的高频追问5.1 几个必须手算一遍的极端用例先列出来面试前建议自己在纸上走一遍空链表A、空链表B直接返回null。双指针法要依赖非空判断否则会出现空指针相关的问题。两个链表中一条为空pA瞬间为空pB在另一条链上走很久最后返回null结果对但效率难看。加了开头判空后这个问题消失。两个链表都只有一个节点且是同一个节点任何解法都会返回这个节点简单。两个链表都只有一个节点但是不同对象哈希法/长度对齐法/双指针法都会返回null但如果你错误地比较了val值且两个节点值恰好都等于同一个数就会返回错误的节点。这种用例就是用来杀“比较值”选手的。两条链表不相交但长度差巨大双指针交换法最坏要走m n个节点才能同时到达null。从这个角度说长度对齐法在“提前判断是否存在交点”这件事上更直接它可以先扫一遍确认尾节点是否相同不相同直接返回。而双指针交换法只能闷头走。5.2 链表带环时这三个解法都失效了吗这个问题属于进阶追问但近年面试出现的频率不低。先说结论带环链表里“相交”的定义需要重新梳理。两条带环链表的相交情况可以分成好几种交点在环外、交点在环入口、交点在环内两条链共享一个环、两条链各自有环但不相交等等。不同情况需要的解法完全不同。哈希法是唯一不需要太多额外思考就能继续工作的方案在遍历过程中记录访问过的节点如果遇到重复节点说明有环也能在环上判断是否命中另一条链表的节点。但长度对齐法和双指针交换法直接套用会出现死循环因为带有环的链表无法通过遍历走到null指针永远不会进入“跳到另一条链表头部”的分支。真要处理带环相交一般步骤是先分别找到两条链表的环入口再用环入口划分链表的结构分情况讨论。这块要展开能单独写一整篇面试里如果被问到能说出“需要先找环入口再分类讨论”这个思路并把最简单的相交场景处理好就算过关了。应对策略是不要慌明确告诉面试官“带环的情况我可以处理但需要先说明相交模型的分类”这比硬着头皮套无环解法体面得多。5.3 只判相交不求交点这是我最喜欢的一道追问因为它的优化空间很反直觉。有人会觉得“我都找到交点了判断相交还需要额外做什么”事实是如果只要求回答“是或否”根本不需要找交点只需要遍历两条链表到尾部比较尾节点引用是否一致。两个链表都无环的情况下尾部节点是同一个对象就必然相交尾部节点不同必然不相交。时间复杂度O(m n)空间复杂度O(1)代码量比求交点的所有解法都少。def isIntersect(headA, headB): if not headA or not headB: return False pa, pb headA, headB while pa.next: pa pa.next while pb.next: pb pb.next return pa is pb这类追问的价值在于考察你能不能针对不同的问题粒度选择不同方案。能否从“求交点”退到“只判断是否相交”反映出你对问题规模的理解不是死记题解而是真正在看题目要求什么。5.4 面试官还会问能不能修改链表结构有些链表相交问题是允许“恢复原状”的也就是用类似“做标记再回滚”的技巧但有些题目明确不允许修改链表。主流解法里哈希法、长度对齐法、双指针交换法都不会修改链表结构所以直接回答“不需要修改原链表即可完成”。如果面试官进一步追问“如果允许修改有没有更巧妙的办法”可以提一句临时把链表A的尾节点接到headB然后问题变成判断链表中是否有环、找环入口最后记得恢复链表。这种方法投机取巧但能体现思路灵活。6. 我的刷题体会先会写再会讲关于两链表相交这道题我在不同阶段对它有过完全不同的理解。第一次接触时我老老实实写了哈希法感觉无比简单后来背下了双指针交换法的七行代码觉得“短小精悍”再后来自己尝试跟别人讲为什么这个简短解法能成立才发现自己其实并不理解它。那种“代码能跑但说不清原理”的状态非常危险面试时一问就露馅。所以我给所有人的建议是这道题不能止步于“把代码默写出来”要能做到闭上眼睛重新推导一次“为什么两个指针会同时到达交点”。推导过程不需要复杂的数学符号就用a、b、c三段长度在纸上画一画十分钟足够。一旦你真正理解了那条“A B”与“B A”等长赛道的原理这道题就不再是背题而是你脑子里随时可以调用的思维工具。最后分享两个自己觉得实用的技巧。第一在写双指针之前先在草稿纸上把两条链表画成上下两行再用箭头模拟指针的跳转路径走两轮你就知道为什么会在交点汇合了。第二如果你对面试官讲这道题建议采用“降级讲法”先给出哈希法作为基线再给出长度对齐法最后给出双指针交换法并且主动说明三种方案在时间、空间上的递进关系。这一套组合拳打下来面试官很难觉得你只是在背答案因为这本身就是一条完整的思考链。