1. 题目背景与题意拆解1.1 相交链表的题目描述聊到LeetCode热题100里链表这块相交链表可以说是最常被翻牌子的题目之一基本算是链表双指针思想的入门代表作。这道题的原题编号是160题目本身不长但很多人在第一次接触时都会栽在“相交”这两个字的理解上。题目给的是两个单链表的头节点headA和headB要求判断这两个链表是否存在相交的节点如果相交就返回第一个相交节点如果不相交就返回null。从表面看这题好像很简单两个链表嘛遍历一遍不就知道了。但实际上真正的难点在于两个链表可能长度不一样它们从某个节点开始共享同一段内存节点而在那之前各自独立。你没法简单地用一层循环去挨个比较因为哪怕两个链表长度相同相交点也可能出现在任意位置更别提长度不同的情况了。我遇到很多同学在第一次自己做这题时上来就写两层循环外层遍历链表A内层遍历链表B逐个节点判断是否相等。这个思路本身没错但时间复杂度是O(m×n)放在面试里基本属于会被追问“还有没有更好的解法”的靶子。所以这道题真正的考察点并不只是“你会不会判断相交”而是“你如何在O(mn)时间内、用O(1)空间完成判断”。1.2 数值相等不等于相交这里必须先强调一个关键点链表中的节点相等指的是指针/引用相等而不是节点里存的val相等。在LeetCode的链表题里节点通常被定义成单链表节点包含一个val字段和指向下一个节点的next字段。判断两个节点是否相交要看的是它们是不是同一个对象也就是内存地址相同。哪怕两个节点的val完全一样next指向也一样它们依然可能是两个独立的节点对象在堆上占用不同的内存空间。判断相交时如果拿val去比较就会出现严重误判明明两个链表没有相交却因为某个节点的值恰好相等而被误判为相交。反过来如果两个链表确实相交了相交节点及之后所有节点的内存地址一定是一致的而val只是它们碰巧牵上了手之后留下的某种属性信息根本不影响判断。所以在写这题时代码里永远是比较头节点指针本身比如if (pA pB)而不是if (pA.val pB.val)。这是新手最容易踩的坑也是面试官非常喜欢在口头追问里埋的一个细节雷区。你可以在白板上把代码写得毫无破绽但如果被问到“你这里为什么比较节点本身而不是比较值”张口答不上来前面的好印象就会打折扣。1.3 哪些条件最容易漏掉除了理解“引用相等”这个核心还有几个边界条件非常值得提前梳理。最典型的就是两个链表中有一个为空或者两个都为空的场景。此时不可能存在相交节点直接返回null即可。有些同学会在代码开头忘了处理空链表结果在进入循环时对空指针解引用直接空指针异常。另一个容易漏掉的场景是两个链表完全独立跑完一遍都找不到相交点。这种情况下双指针解法能优雅退出但如果你用的解法依赖于“找长度差”就必须仔细处理长度差计算否则会出现下标越界或者死循环。还有一种场景两个链表本来就是一个链表的开头就是另一个链表的某个节点甚至两个链表从头节点开始就完全相同。这时候相交点就是头节点自身很多解法如果写得不够严谨会在这一条上翻车。后面我会在边界情况那一节专门展开讲这几种场景的代码处理方式这里先留个印象。2. 两种经典解法哈希集合与双指针2.1 哈希集合解法——最稳的暴力拿到这道题如果只想快速通过哈希集合是最稳的写法。思路非常直观先把链表A的所有节点依次存入一个哈希集合HashSet然后遍历链表B逐个节点判断这个节点是否已经在集合里出现过。第一个出现的节点就是相交节点遍历完整个B都没有发现就说明两个链表没有相交。这个解法我强烈建议每个初学者都先写一遍原因有两个。第一它特别容易理解几乎不存在写错的可能性第二它是后续优化解法的最佳对照物你能直观感受到空间复杂度从O(m)压到O(1)带来的提升而不是单纯被要求背一个看起来很巧妙的双指针模板。代码写起来大概是这样def getIntersectionNode(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注意这里存进集合的是节点对象本身不是节点的val原因上一节已经说过了。另外一个细节是Python里set存储自定义对象时可以作为哈希键使用因为链表节点默认的哈希是基于对象身份的恰好符合我们这里的需求。时间复杂度是O(mn)因为要完整遍历两个链表各一次空间复杂度是O(m)因为要把链表A的所有节点都存进集合里。面试时如果问复杂度你要能说清楚这里的m是链表A的长度而不是较长的那个虽然无伤大雅但表达清晰总是加分项。2.2 双指针解法——空间换时间哈希解法的缺点很明显空间复杂度O(m)在链表很长时并不理想。LeetCode的进阶要求里写得明明白白能否设计一个时间复杂度O(mn)、仅用O(1)内存的解决方案。既然要求O(1)额外空间那自然不能借助外部数据结构只能靠指针在链表之间移动来找出答案。于是引出双指针法也是这道题最重要的核心思想。两个指针pA和pB分别从headA和headB出发每次各走一步。当pA走到链表A的末尾时让它跳转到链表B的头节点继续走当pB走到链表B的末尾时让它跳转到链表A的头节点继续走。直观上看这个操作等于把两个链表拼接成了两条新路径让两个指针走相同的路程从而消除长度差带来的错位。这个解法被称为浪漫解法不是没有原因的网上一搜相关讨论必能看到有人拿“你走过我走过的路我们就会相遇”来描述这个算法。作为段子确实很有趣但面试的时候可不能只说浪漫你得能从数学和逻辑上解释清楚为什么这样做能保证相遇。2.3 为什么优先推荐双指针哈希解法虽然容易写但面试的考察重点往往不在“能不能做出来”而在“能不能做到最优”。LeetCode热题100里的题目基本都经过层层筛选每一道背后都代表一类经典解法相交链表对应的就是链表双指针技巧。面试官让你做这题十有八九是想看看你有没有掌握那个O(1)空间的双指针思路。从另一个角度说双指针解法不仅是这一道题的工具它和环形链表检测、链表倒数第k个节点、合并两个有序链表等题目都共享类似的思想内核。把双指针练熟了相当于获得了一把能开多把锁的钥匙。后面我会专门把双指针的推导过程写透因为只有真正理解推导逻辑才可能在白板上从容地写出无bug版本。再说说两者的适用场景如果是在本地刷题做题时间和内存限制都不紧张哈希解法完全够用如果是面试场合一定要先聊双指针解法。哪怕你最后写的代码是哈希版本也最好能在一分钟内把双指针思路讲清楚这会让面试官觉得你是有意识地选择了方案而不是只会背一种模板。3. 双指针的完整推导与代码落地3.1 从路径角度看相遇要理解双指针为什么可行最直观的方式是把两个指针各自经过的路径拉出来看。链表A的总长度记为a链表B的总长度记为b两个链表相交部分长度为c。那么在相交之前链表A独有部分的长度是a-c链表B独有部分的长度是b-c。指针pA如果不进行跳转走完链表A需要a步pB走完链表B需要b步。此时如果a和b不相等两个指针根本不可能在相交节点处同时出现——它们到达相交节点的时机是错开的。这就是为什么朴素双指针不可行的根本原因。现在加入跳转操作pA走完A之后跳到B的头部继续走pB走完B之后跳到A的头部继续走。我们来看pA走到链表的末尾之前要经过哪些部分它先走完链表A的全部a步再走链表B的独立部分b-c步总共a(b-c)步。pB呢它先走完链表B的全部b步再走链表A的独立部分a-c步总共b(a-c)步。你算一下这两个总路径长度a(b-c)和b(a-c)展开之后都是ab-c完全相等。也就是说两个指针在跳转之后走的总路程是一样的它们会在同一个时刻到达它们路径中的同一个位置。这个位置在哪里仔细看路径组成pA路径中最后一段是“链表B的独立部分相交部分”pB路径中最后一段是“链表A的独立部分相交部分”而它们的总长度相等所以相交出现时两个指针必定同时踩在相交部分的第一个节点上也就是我们要找的答案。如果两个链表根本不相交可以把不相交理解为c0那么pA总路径是abpB总路径也是ab最终它们会在走完所有节点后同时走向null也就是都变成空指针此时返回null即可。这个数学推导并不复杂但亲手推一遍远比背结论扎实得多。3.2 代码实现Python基于上面的推导代码写起来非常简洁。Python版本的实现大概长这样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我来说说这里几个容易被忽略的细节。很多人第一次写时会用pA.next判断是否到末尾但正确的是在pA为null时跳转到另一个链表的头节点而pA.next为null只是表示这是尾节点还不应当跳转。两种写法只差一个执行时机但对判断结果影响不大不过从逻辑严谨性上看用“当前指针是否为null”作为跳转条件更贴合推导过程。循环条件pA ! pB是在两个指针都非空的前提下进行判断的。如果两个链表不相交最终两个指针会同时变为nullnull等于null循环退出此时返回null。如果相交则两个指针会在相交节点相遇循环也在那里退出返回的就是要找的节点。这里不需要额外的计数器因为前面已经证明两个指针绝不会一个已经走到null另一个还在链表中间晃荡——它们总是一前一后到达终点然后同时进入null状态。还有一种常见写法是用一个计数器统计两条链表的遍历次数防止“绝不会相遇”的极端情况死循环。其实这个担心是多余的因为双指针最坏情况下只需要走mn步就会收敛不存在无限循环的可能。只要跳转时机写对不需要额外的状态变量。3.3 C版本的标准写法用C写这题也很常见尤其很多人面C岗位时会被要求现场写一遍。C版本的代码在结构上几乎一模一样只有语言细节不同struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA nullptr || headB nullptr) { return nullptr; } ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; }这里的条件运算符写法非常常见不过要当心一个问题如果某个链表的头节点本身为空那么在进入循环前就已经返回null了所以循环里不需要再判断链表初始是否为空。另外C里空指针和空指针比较是合法的两个nullptr比较结果为true所以循环能正常退出。如果你用的是Java思路完全一样只是代码里把nullptr换成null把ListNode指针换成引用而已这里就不再单独贴一份了。关键是理解这一类题对语言的依赖程度很低真正值钱的是那个路径等长的思路。4. 边界情况与常见问题排查实录4.1 无相交的场景先说说两个链表完全独立、没有任何一个共同节点的场景。这是双指针解法最好理解的一种情况pA走完A再走BpB走完B再走A两条路径总长度相等且互不相交最终两者都在走完自己的整条路径后同时到达null循环退出返回null。我在实际调试中见过有的同学在这个场景下死循环原因往往是跳转条件写成了“当前节点的next为空再跳转”导致其中一个链表更长时短链表对应的指针已经跑到null了却还在循环体内被继续解引用。比如链表A很长链表B很短pB会先一步走完B然后跳转到A而pA还在B上慢慢走。如果代码逻辑在pA已经到达null之后仍然尝试访问pA-next就会空指针异常。这里有个实用的小技巧在本地测试无相交场景时可以构造两个完全独立的链表每个链表长度为3到5个节点手动模拟一遍双指针的行走过程。你会发现指针并不是“同时走到null”而是先后经历跳转最后“同时变成null”。这个模拟过程能帮你理解很多边界细节远比自己空想有效。4.2 链表为空的场景链表为空的情况其实最简单但很多人会在代码的入口处漏写判断。如果允许带空指针进入主循环C版本里pA和pB会有一个是nullptr直接进入pA ! pB的判断此时两个指针一个null一个非null自然不相等然后执行pA和pB的更新。如果两个链表都为空两指针都为null循环不进入直接返回null。看起来似乎也能正确返回但问题是如果写成“先判断再解引用”的代码风格空链表会在某个指针更新语句中触发空指针访问所以入口处的空节点判断依然是必要的最佳实践。严格来说从纯逻辑角度讲空链表判断不是必须的双指针算法本身能处理空链表。但面试写代码时显示你对空指针的敏感度是好事。我的建议是保留这两行入口判断因为它们能让代码在语义上更清晰链表为空自然没有相交节点可言。4.3 开头即相交的场景两个链表从各自的头节点开始就共享节点这种情况比较隐蔽。举个例子链表A的头节点就是链表B的头节点也就是说headA和headB指向同一个节点。此时无论两个链表后面的内容是什么相交点就是头节点本身。在双指针代码中循环一开始就会判断pA ! pB发现两者相等直接返回pA整个过程只判断了一次。这个行为完全符合预期不需要专门写分支处理。但哈希解法呢如果把链表A的所有节点都放进集合然后遍历链表B时第一个节点就命中直接返回也完全没问题。还有一种更隐蔽的变体两个链表长度相同从某个中间节点开始相交。这种情况下双指针不需要跳转就能相遇因为它们的步调天然同步。只有两个链表长度不同时跳转机制才会真正发挥作用。所以准备测试用例时至少应该准备三类长度相同相交、长度不同相交、长度不同不相交覆盖三种核心路径。4.4 面试现场提问的常见变体面试官很少会只让你写完这题就放你走通常会追加几个变体问题。最常见的是“如果链表里可能有环你怎么判断相交”这个问题比原题复杂得多因为环的存在让“走完再跳转”的策略失效——链表在环里会无限循环无法正常走到末尾。我的建议是遇到这种问题时不要急于回答先和面试官对齐需求。如果两个链表各自可能有环需要先判断环的入口并用快慢指针找出相遇点然后分情况讨论。如果确认两个链表没有环才能使用上面讲解的双指针解法。面试官抛出这类变体通常是想考察你对“算法适用条件”的敏感度而不是真的指望你在几分钟内写出一个完整的多分支处理方案。另一个常见追问是“你如何证明两个指针走的总路程一定相等”这个问题直接对应前面3.1小节的推导过程。建议你在准备时把数学公式推两遍做到能在白板上流利写出路径等式。很多同学代码能AC但被问到证明时支支吾吾这是很明显的准备不足信号。5. 复杂度对比与面试表达建议5.1 两种解法的复杂度对照把两种解法放在一起对比能更清楚地看出它们各自的定位。哈希解法的时间复杂度是O(mn)空间复杂度是O(m)这里的m是第一个链表的节点数。双指针解法的时间复杂度是O(mn)空间复杂度是O(1)因为除了两个指针变量外没有任何额外数据结构。需要特别注意的是双指针虽然时间复杂度看起来和哈希解法一样但实际常数项更小。哈希操作涉及计算哈希、处理冲突、可能的扩容每个节点入集合和查集合都有额外开销。而双指针只是单纯的指针移动和比较在链表长度达到数十万甚至百万级别时两者的运行时间差距会相当明显。LeetCode上的测试数据规模不大所以两种解法在判题机上都是秒过但如果你在面试里主动提一句“双指针的常数项更小、不需要哈希开销”会成为口试环节的一个加分点。这里贴一个简单的对比如下解法时间复杂度空间复杂度额外数据结构适用场景哈希集合O(mn)O(m)需要HashSet理解门槛低、编码简单双指针O(mn)O(1)不需要面试标准答案、内存受限5.2 面试时如何口述解题思路面试时讲题和平时刷题完全是两种状态。平时你可以对着IDE静心调试但面试要在短时间内把思路讲清楚。我建议按以下顺序组织口述先从最简单直观的解法讲起也就是遍历A存哈希、遍历B查交集把时间复杂度和空间复杂度都明明白白说出来。然后话锋一转说“但这个解法空间复杂度偏高我们可以优化到O(1)”紧接着引出双指针思路。讲述双指针时不要只背结论最好按照三个步骤展开。第一步说明两个链表长度可能不等导致直接同步遍历会错位。第二步说明通过让指针到达末尾后跳到另一条链表的头部可以消除长度差的影响。第三步用公式说明两条路径长度相等从而证明两个指针必然同时到达相交节点或同时到达null。这个过程别背稿子最好在白板上画一个简单示意图。画法也很简单先画两个相交链表把公共部分涂黑然后分别画出pA和pB的遍历路径用箭头标注跳转的位置。面试官看到你能画出清晰的过程图整体评价会明显提升。5.3 从这道题延伸到其他链表问题相交链表只是链表双指针体系的冰山一角。把它吃透之后环形链表检测快慢指针判断是否有环、环形链表II找环的入口、删除链表倒数第N个节点、链表中间节点等问题都会变得顺手很多。因为它们的底层逻辑都依赖“两个指针在链表上以不同速度或不同起点移动”这个基本框架。有一个很实用的延伸思考双指针法的本质是“通过拼接路径使两个指针的步调对齐”这个思想在双向链表、树上的路径问题、甚至某些数组题目中也能用上。比如求两个不重叠数组区间是否有交集路径对齐的思想同样成立。虽然解法形式上差异很大但抽象层次上是一致的。如果你正在准备面试我强烈建议把这道题放到“链表双指针专题”里和另外三四道题一起复习而不是单独刷完就完事。一轮专题刷完你会明显感觉到对链表的“手感”上来了再看到新的链表题时第一反应不再是生搬硬套而是先判断出适合哪种指针策略。这个东西靠经验积累刷题量不够是很难速成的。我在带别人准备算法面试时经常用的训练方法是刷完这道题后自己闭着眼睛把双指针的推导过程默写一遍再把Python代码默写一遍然后再试试用C写一遍。三种语言版本都能写顺了这题才算真正过关。最后一句话链表题的边界情况非常多但相交链表只要抓住“引用相等”和“路径等长”这两个关键点整道题就像被拆掉引线的地雷怎么碰都不会炸。