前阵子在给几个朋友讲链表题的时候我发现“相交链表”这道题几乎每次都会被拎出来讨论。它看起来就是一个简单的双指针问题代码不过十行。但当你真正把它讲透从暴力解法一步步走到最优解再去想边界条件和各种变体的时候会发现这里面藏着的细节远比想象中多。这篇文章我就以“每日一题”的视角把相交链表从头到尾拆一遍包括问题定义、几种解法的思路演变、数学推导、实战代码以及我自己踩过的坑和总结的验证用例。1. 相交链表到底在考什么问题定义与隐含条件1.1 什么才算真正的“相交”题目本身并不复杂给定两个单链表的头节点要你找出两个链表相交的起始节点。如果两个链表没有交点就返回空指针。这里最容易被忽略的是“相交”的精确定义。很多初学者第一次做这道题会误以为两个链表中某个节点的值相等就算相交。这是完全错误的。真正的相交指的是从某个节点开始两个链表在内存中共享同一批节点也就是说nodeA nodeB这个比较是基于引用地址的而不是基于nodeA.val nodeB.val。举个例子链表 A 是1 - 2 - 3 - 4链表 B 是5 - 6 - 3 - 4。如果这里的3 - 4是内存中同一份节点那么它们确实相交于值为 3 的节点。但如果你只是创建了两个各自独立的链表恰好它们的后半段数值也是3 - 4那这两个链表毫无关系返回的结果应该是空。可以这么理解单链表中的每个节点在内存里只有一个唯一的地址。当一个节点的next指针指向另一个节点时它们是“物理上”连接在一起的。两个链表相交之后从交点开始的所有节点都是同一批节点两个链表共享这片区域。所以判断相交本质上是在判断两条“链”是否在某一点之后合并成了同一条“链”。1.2 为什么这道题适合作为“每日一题”我个人的感受是一道好的“每日一题”不应该太难也不应该太简单。它最好具备以下几个特点解法层次分明。暴力法可以解哈希表可以解双指针也可以解。不同水平的读者都能找到自己能理解的方案而且每种方案之间的演进逻辑非常自然。面试高频。链表操作本身就是面试中的常客而相交链表几乎涵盖了链表题的所有核心考点指针遍历、边界处理、复杂度分析、数学推导。便于扩展追问。面试官很容易从这道题延伸出“如果链表有环怎么办”“能不能不用额外空间”“如何判断两个链表是否相交”等问题。一道题可以变成一串题。每天花二三十分钟把这道题从暴力的O(m*n)优化到双指针的O(mn)再把推导过程写清楚远比一口气刷十道简单题更有收获。这也是我为什么愿意专门写一篇长文来聊它的原因。2. 先看两个基础解法暴力遍历与哈希集合2.1 暴力双层循环最直观但不建议在面试里直接写拿到题目最容易想到的思路一定是对于链表 A 中的每一个节点遍历一遍链表 B看看有没有节点和当前节点相等。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA headA; while (pA ! null) { ListNode pB headB; while (pB ! null) { if (pA pB) { return pA; } pB pB.next; } pA pA.next; } return null; }这个解法的正确性不用怀疑。只要两个链表有交点外层循环肯定能遍历到那个交点内层循环也肯定能匹配上它。时间复杂度是O(m*n)空间复杂度是O(1)。但问题也很明显如果两个链表都很长这个解法会非常慢。在面试场景中如果你一上来就写这个代码面试官通常不会满意。写完暴力解法后一定要主动说“这个解法时间复杂度太高我们可以用哈希表来优化”然后再给出更优方案。2.2 哈希集合解法思路清晰、时间最优暴力法的瓶颈在于内层循环每次都要从头开始线性扫描链表 B。如果能借助哈希表的快速查找能力把“判断 B 中是否存在某个节点”的时间从O(n)降到O(1)总时间就是O(mn)。具体做法是先遍历链表 A把所有节点都放进一个HashSet再遍历链表 B依次检查当前节点是否已经存在于集合中。第一个存在于集合中的节点就是交点。def getIntersectionNode(headA, headB): seen set() pA headA while pA: seen.add(pA) pA pA.next pB headB while pB: if pB in seen: return pB pB pB.next return None哈希表解法的时间复杂度已经是O(mn)这达到了时间上的最优。但它引入了O(m)的额外空间。如果题目没有明确要求空间复杂度这个解法完全可以接受。在实际面试中如果你一时想不出双指针解法先给出哈希表方案是一个很稳妥的选择。接下来再告诉面试官“我还能继续优化把空间复杂度降到O(1)”这就自然过渡到了双指针解法。3. 双指针解法一步消除长度差的优雅思路3.1 核心思想与代码实现双指针解法是这道题最经典的解法代码短到令人发指但第一次看到的人往往会愣一下为什么两个指针各自走完自己的链表后再跳到对方的链表头继续走就一定能相遇先看代码public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA headA; ListNode pB headB; while (pA ! pB) { pA (pA null) ? headB : pA.next; pB (pB null) ? headA : pB.next; } return pA; }就这么几行。两个指针pA和pB分别从headA和headB出发同步向后移动。当一个指针走到链表末尾也就是变为null时它不停止而是跳到另一条链表的头节点继续走。如果两个链表相交两个指针最终会在交点相遇如果不相交它们最终会同时到达null然后退出循环。3.2 一步步拆解两指针相遇的数学推导要理解这个解法关键在于搞清楚两个指针分别走了多少步。假设链表 A 的独立部分长度为a链表 B 的独立部分长度为b两个链表的公共部分长度为c。这里说的“独立部分”指的是从各自的头节点到交点之前的那些节点公共部分则是从交点到链表末尾的所有节点。两个指针开始同步移动。pA先走完链表 A 的全部节点独立部分a加上公共部分c一共a c步然后pA变为null。按照规定pA跳到链表 B 的头节点继续走链表 B 的独立部分b。当pA走到交点时它总共走了a c b步。再看pB。它先走完链表 B 的全部节点独立部分b加上公共部分c一共b c步然后变为null再跳到链表 A 的头节点继续走链表 A 的独立部分a。当pB走到交点时它总共走了b c a步。a c b和b c a是相等的。也就是说当两个指针都走了a b c步的时候它们同时到达了交点。交点的存在让两个指针在遍历完两条链表的总长度之后恰好汇聚在同一个节点上于是pA pB循环退出返回这个节点。如果两个链表不相交那么公共长度c 0。两个指针分别走完a b步之后都会变成null。此时循环条件pA ! pB不成立退出循环返回null。这个结果同样是正确的。这个解法的精妙之处在于它通过“互相交换链表继续走”的方式人为地把两个指针的路程拉齐了。可以把它类比成两个人在两条不同长度的跑道上跑步跑完自己的跑道后换到对方的跑道继续跑。只要两条跑道最终汇聚到同一条路那么两个人一定会在汇聚点相遇。3.3 三种语言版本与复杂度对比除了上面 Java 版本我也把 Python 和 C 的版本一并写出来方便不同语言背景的读者对照。def getIntersectionNode(headA, headB): 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 pAListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; }三种语言的逻辑完全一致唯一需要注意的是比较方式Java 中对象的比较的是引用地址Python 中要用is而不是C 中指针的直接比较地址。这些都是符合题目“判断节点是否相同”的要求的。三种解法的复杂度对比如下解法时间复杂度空间复杂度备注暴力双层循环O(m*n)O(1)代码简单但性能最差哈希集合O(mn)O(m)时间最优但占用额外空间双指针O(mn)O(1)时间、空间同时最优从面试沟通的角度我建议的表述顺序是先分析暴力法的问题再说哈希表如何优化最后抛出双指针实现空间上的优化。这样一层一层递进能让对方感受到你的思路是清晰的而不是背模板。4. 写代码时最容易掉的坑与自测用例清单4.1 空指针判断的经典误区双指针解法的代码虽然短但里面有一个非常容易写错的地方应该用pA null来判断指针是否已经走完了整条链表而不是用pA.next null。有些人会写成这样while (pA ! pB) { pA (pA.next null) ? headB : pA.next; pB (pB.next null) ? headA : pB.next; }看起来好像也能跑但这里面埋着两个问题。第一个问题当链表为空或者链表只有一个节点时pA.next可能会触发空指针异常。比如headA本身就是一个空链表那pA初始就是null这时候访问pA.next直接报错。第二个问题用pA.next null判断“链表走完了”意味着指针停留在链表的最后一个节点上而不是越过最后一个节点到达null。这在某些情况下会改变指针的行走路径。正确做法是让指针真正走到null再切换到另一条链表。因为交点有可能恰好就是链表的最后一个节点。如果使用pA.next null作为切换条件那么你在到达交点的前一步就已经切换了会直接跳过交点。我记得最初写这个解法时就犯过这个错误怎么测都觉得结果不对劲后来一步步调试才发现是切换时机的问题。记住一个判断准则只有当指针完全离开一条链表时才切换到另一条链表。所谓“完全离开”就是指pA变成了null。4.2 死循环风险与“不可能相等”的理解另一个值得注意的点是为什么两个链表不相交时while循环不会变成死循环原因其实已经在数学推导中说过了。不相交时c 0pA走完a b步变成nullpB也走完b a步变成null两者同时到达null。既然pA和pB都等于null循环条件pA ! pB不再成立自然就退出了。还有一种不太容易察觉的风险来自对“相等”的误判。如果代码里不小心把引用比较写成了值比较比如while (pA.val ! pB.val) { ... }那问题就大了。因为不同链路上的节点完全可能拥有相同的值两个指针可能因为值相等而错误地“相遇”也可能因为值一直不相等而无限循环。所以一定要记住这里比较的是pA pB也就是引用地址绝对不要去碰pA.val。4.3 一套完整的自测用例自己做算法的本地验证时我习惯先把边界用例列出来再写代码这样能省去很多反复调试的时间。对于相交链表这道题我通常会用下面这组用例来检验解法用例预期结果测试目的两个链表不相交null验证循环能正常退出headA 为空链表null验证空链表处理两个链表都为空null验证极端空输入两个链表完全重合headA headB直接返回 headA验证 a、b 都为 0 的情况交点在链表 B 的中间位置返回交点验证常规相交交点恰好是两条链表的最后一个节点返回该节点验证“最后一个节点也是交点”的边界一个链表只有一个节点且该节点就是交点返回该节点验证最短链表与交点重叠的情况有了这份用例清单不管是用在线刷题平台的测试环境还是自己本地写一个简单的测试脚本都能快速发现问题。5. 从这道题延伸开去长度差解法、带环变体与真实场景5.1 长度差法另一个 O(mn) 解法双指针并不是唯一的O(mn)思路。还有一种更直白的方法先分别求出两个链表的长度算出长度差让较长的链表先走长度差那么多步然后两个指针同步前进第一个相遇的节点就是交点。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA 0, lenB 0; ListNode pA headA, pB headB; while (pA ! null) { lenA; pA pA.next; } while (pB ! null) { lenB; pB pB.next; } pA headA; pB headB; if (lenA lenB) { int diff lenA - lenB; while (diff-- 0) { pA pA.next; } } else { int diff lenB - lenA; while (diff-- 0) { pB pB.next; } } while (pA ! pB) { pA pA.next; pB pB.next; } return pA; }这个解法的好处是思路特别容易解释两个指针如果处在“距离交点同样远”的位置上那么同步前进一定能同时到达交点。为了实现这一点我们先把长度差消掉。它和双指针解法的时间复杂度都是O(mn)空间都是O(1)只是代码量略多一些。面试时如果你觉得双指针的推导绕也可以先讲长度差法再说“其实还能用双指针让代码更精简”。两种解法掌握其中一个就够用但两个都懂会更有底气。5.2 如果链表带环题目立刻变难标准的相交链表题目默认链表没有环。但面试官很可能追问“如果链表里有环还能用双指针吗”这个问题会直接把难度拉高一个档次。因为一旦存在环原来的双指针遍历就不可能走到null也就无法通过“交换链表继续走”的方式消除长度差。处理带环情况的一般思路是先用快慢指针判断两条链表是否各自有环。如果有环找到环的入口节点。分析交点可能在环前、环上还是环后的不同情况再进行相应处理。这道题从 Easy 变成了真正棘手的 Hard。我在实际面试模拟中遇到过几次追问如果你能把“先判环、再分类讨论”的框架说清楚面试官通常就会满意了。不需要当场把完整代码写出来。5.3 我在实际开发中感受到的“相交”思想最后聊一点我在实际开发中体会到的、和这道题相关的思想。“两个链表找交点”这个场景本身在实际业务中不常直接出现。但它的核心思想——用两个同步指针消除长度差、寻找重合点——在很多地方都有类似的应用。比如版本管理中两个分支的合并点可以理解为两条提交记录链的“相交”再比如代码编译过程中不同路径的控制流汇合到同一个基本块本质上也是一种“相交”。更重要的是这道题让我意识到很多看似“技巧性”的算法其实都是在回答同一个问题如何在不额外记住太多信息的情况下利用行走路径本身来传递信息。双指针没有使用任何额外空间却通过交换链路的策略“记住”了自己走过了两条链表。这种思路没法靠死记硬背学会只能通过大量练习慢慢培养直觉。拿这道题当作每日一题来刷可能只需要一天。但把它彻底理解透包括每种解法的推导、边界条件、变体问题花上一周都不算多。我个人最深的一个体会就是题目本身不复杂复杂的永远是那些你以为已经懂了、但一写就错的细节。希望这篇文章能帮你把这些细节一次理清。