我最近在整理自己的每日一题笔记正好写到相交链表这道经典题。它是LeetCode第160题也是链表模块里面试出现频率极高的一个。原题有很多马甲比如找两个单链表的交点、判断两条链表是否合并过但内核都是同一件事给定两条单链表找到二者开始相交的那个节点如果没有任何交点返回null。这题非常适合正在刷算法题准备面试的人也适合刚学链表不久、想拿一个典型题目练手的新手。它考察的东西很实在你对链表结构的理解是不是停留在“值相等”的层面以及你懂不懂双指针这类遍历技巧。我第一次做这道题时翻了个很经典的错误——以为找到值相等的节点就是相交结果被测试用例教做人了。今天把这道题从审题到最优解完整拆一遍顺便把那些常规题解里不会写的坑都列出来。1. 先把题读明白相交链表究竟在求什么1.1 题目说人话版题目原文有一大段背景设定翻译成人话就是给你两条单链表它们可能在某个节点之后完全共用一条链像字母Y那样先分开后合并。你要找到那个“分叉合流点”也就是第一个被两条链表共同拥有的节点。如果没有这种节点就返回null。需要注意的是这个“共同拥有”在链表里必须理解成节点本身被同时引用也就是两个链表走到了同一个内存地址而不是两个节点恰好存了相同的值。底层逻辑是单链表的节点里只有一个next指针指向下一个节点。一旦两个指针指向同一个节点那么从这个节点开始后续所有节点必然完全一致因为再也分不开了。这也是为什么相交链表在图上一定是Y字形而不可能是X字形——X字形意味着两个节点合并又分开这在单向链表里根本做不到。1.2 最常见的审题翻车点我见过很多刷题的人在这道题上栽跟头包括我自己本质上都是没分清“值相同”和“节点相同”。举个例子链表A是 1 - 3 - 5链表B是 2 - 3 - 6。这两个链表里都有值为3的节点但它们各自是独立分配的节点只是内容恰好相同。用代码表示就是nodeA.val nodeB.val但nodeA和nodeB指向不同的地址。题目要的不是这种“貌似相交”而是nodeA nodeB这种“真·同一个节点”。为什么这个区别这么关键因为如果你按值去判断只靠几个简单用例根本测不出来但提交后就会遇到各种构造好的测试数据。面试现场如果写错这个逻辑面试官一眼就能看出来你理解的是“数组”而不是“链表”。还有一个容易忽视的点题目默认这两个链表都没有环。LeetCode原题的说明里明确规定了这一点。如果你在面试中被追问“如果有环怎么办”那是另一道变体题后面我会单独讲一下处理思路。1.3 这个考点为什么被面试官偏爱相交链表在面试中受欢迎不是因为算法本身有多高级而是因为它能把候选人的基础功底问得很透。考察点至少有三个第一个你知不知道链表节点是由地址/引用维系的而不是值。这是数据结构的底层认知。第二个你愿不愿意主动分析时间和空间复杂度。题目很容易写出一个O(n*m)的暴力做法但好的解法需要把复杂度降到O(nm)。面试官就是想看你能不能主动优化。第三个你懂不懂双指针这种“无额外空间的遍历技巧”。这是链表题的常青考点会了这道题后面做环形链表、删除链表倒数第N个节点都会顺手很多。所以这道题看起来是“每日一题”其实是性价比很高的题目。2. 最容易上手的哈希集合法2.1 思路一句话版本先把一条链表的所有节点存进一个哈希集合再遍历另一条链表第一次遇到“已经在集合里”的节点那就是交点。如果整条遍历完都没有说明两条链表不相交。为什么哈希集合可行因为集合里存的是节点引用判断时也是按引用去比较天然满足“同一个节点”这个精确语义。而且哈希集合的查找平均是O(1)所以整体性能不差。2.2 代码实现与逐步拆解用Python写起来非常直白def get_intersection_node(headA, headB): visited set() cur headA while cur: visited.add(cur) cur cur.next cur headB while cur: if cur in visited: return cur cur cur.next return None拆开看就三步第一步从headA出发把沿途每个节点都放进set注意放的是节点对象本身不是cur.val。 第二步从headB出发每走一步都问一句“这个节点在不在刚才那个set里”。 第三步如果B链的某个节点命中直接返回如果B走完都没有返回None。2.3 哈希法的适用场景与局限哈希法的优点是逻辑简单不容易错适合作为面试时的“第一版答案”。你完全可以先跟面试官说我先用哈希集合做一个最容易理解的版本再考虑优化空间。它的局限也很明显额外的空间复杂度是O(n)需要保存一条链的全部节点。在面试里面试官大概率会追问一句“能不能把空间复杂度降到O(1)”。这时候就能顺理成章地引出双指针解法。这里还有一个实操小技巧在判断“cur in visited”之前不需要对cur判空因为当cur为None时None不在集合里而while循环的条件也保证了cur不会是None除非headB本身就是空链表。如果headB是空链表第二个while压根不进入直接返回None结果也是对的。提示哈希集合必须存节点不要存节点值。存节点值的代码跑再多次也过不了完整的测试用例。3. 最优解用双指针破解相交链表的完整推演3.1 核心思想把两条路接成一条路双指针解法是这道题最精彩的版本同时也是网上流传最广的版本。我第一次看到这个解法时第一反应是“这是什么魔法”后来拿两个链表手动推了两遍才真正明白它背后的数学逻辑。逻辑是这样的维护两个指针pA和pB分别从headA和headB出发。两个指针每次各往前走一步。区别在于走得快的那个指针如果走到了链表尾部达到null就从另一条链表的头部重新进链表继续走另一个指针同理。这么循环往复直到两个指针相遇。相遇的那个节点要么是交点要么是null。用一句话概括每个指针最终走完的路程都是链表A的长度加上链表B的长度。在这个“同步总路程”的前提下两个指针天然消除了长度差。如果两条链表有交点它们必然会在交点相遇。3.2 链表长度与节点数的数学关系假设链表A的长度是L1链表B的长度是L2相交部分长度是C。这里C是两条链共享的那一段节点数。如果从headA出发先走完自己的L1步再切到headB继续走想走到交点还需要走多少步答案是L2 - C步。因为在B链表里交点之前的节点就是L2 - C个。所以pA从出发到交点一共走了 L1 (L2 - C) 步。如果从headB出发先走完自己的L2步再切到headA继续走想走到交点还需要走 L1 - C 步。所以pB从出发到交点一共走了 L2 (L1 - C) 步。两个式子算一下L1 L2 - C L2 L1 - C发现是完全相等的。这就解释了为什么两个指针一定会在同步推进的过程中于交点相遇。它们虽然起点不同、各自先走的长短也不同但只要是“先走完自己的再去走别人的”总步数就会被拉平。如果两条链表根本不相交也就是C 0上面的计算会变成pA走了L1 L2步后停在nullpB走了L2 L1步后也停在null。因为空指针和空指针是相等的循环照样会终止结果返回null不会死循环。3.3 具体推演相交链表双指针全过程光看公式还是不够直观我特意构造了一个具体的链表对把每一步的指针位置写出来你就明白它有多优雅了。构造如下链表Aa1 - a2 - c1 - c2 - c3 - null 链表Bb1 - b2 - b3 - c1 - c2 - c3 - null这里的c1就是交点。链表A长度是5链表B长度是6公共部分是c1、c2、c3公共长度C 3。双指针同步推进每一轮变化如下轮次pA位置pB位置是否相交0a1b1否1a2b2否2c1b3否3c2c1否4c3c2否5nullc3否6b1null否7b2a1否8b3a2否9c1c1是看最后两行虽然两个指针之前的“身世”完全不同但在第9轮双双站到了c1上。pA经历了完整的链表A又走过了链表B交点和交点之前的b1、b2、b3pB经历了完整的链表B又走过了链表A交点和交点之前的a1、a2。二者总步数完全相同交点也完全相同。3.4 不相交时为什么也不会死循环很多第一次接触这个解法的人会担心如果不相交两个指针会不会永远互相追不上答案是并不会因为最后都会变成null。同样做一个简单推演。链表Aa1 - a2 - a3链表Bb1 - b2。两者长度分别是3和2。轮次pA位置pB位置0a1b11a2b22a3null3nulla14b1a25b2a36nullnull两个指针最终在null处相等循环正常终止返回null。因为pA一共走了L1 L2 1个位置包括最后那个nullpB也一样步数一致双方同步抵达终点。这里有一个细节值得注意指针从null跳到另一条链表头部这件事本质上是把“两条链表拼接起来”。pA走的路径等价于A链表接到B链表后面pB走的路径等价于B链表接到A链表后面。如果相交拼接后的两条长链从交点开始共享相同后缀如果不相交拼出来的两条长链也一样长最后同时走到null。3.5 代码实现Python / Java 双版本双指针代码非常短但正因为短初学者容易背错。我在这里列出两个常用版本。Python版本def get_intersection_node(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 pAJava版本public 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; }写这个代码有几个容易出错的地方我挨个说第一个是判空。如果在循环内部用pA.next判断是否到达尾部千万别忘记当pA已经为null时也会走到这个分支所以要先判断pA本身是否为空。第二个是跳转时机。pA变到null的下一轮才跳转到headB而不是在最后一个有效节点时就跳转。换句话说链表A完全走完指针变成null之后下一步才从headB重新开始。这样保证总路程确实是L1 L2而不会因为提前跳转导致路程变短。第三个是while条件。循环条件必须是pA ! pB而不能是pA.next ! pB.next。因为两个链表不相交时最终相遇的位置是null如果用next去判断会在pA或pB为null时直接报错。注意这个解法在LeetCode上的时间复杂度是O(m n)空间复杂度是O(1)属于题目要求范围内的最优解。4. 其他常见思路与解法对比4.1 长度差法除了双指针还有一类常见解法叫“长度差法”在工程场景和教学里也很常出现。思路不复杂先分别求出两条链表的长度然后让较长的链表指针先走长度差这么多步把两条链表的“起跑线”对齐再同步往前走第一次相遇的节点就是交点。Python代码是这样的def get_intersection_node(headA, headB): def get_length(head): length 0 while head: length 1 head head.next return length lenA, lenB get_length(headA), get_length(headB) pA, pB headA, headB diff abs(lenA - lenB) if lenA lenB: for _ in range(diff): pA pA.next else: for _ in range(diff): pB pB.next while pA ! pB: pA pA.next pB pB.next return pA这个解法的优点是逻辑非常直观容易向面试官解释也不会出现“为什么两个指针能相遇”这种让人挠头的疑问。缺点是代码相对长需要多写一个求链表的函数而且要知道两条链表的长度后才能开始对齐。从面试的角度讲你可以先讲长度差法再讲双指针法展示你思路的递进过程。两种解法的复杂度都是O(m n)时间O(1)空间实际运行效果几乎没有差别。双指针的代码更短但理解门槛更高长度差法的代码更长但逻辑更接地气。4.2 解法对比表我把这道题常见的几种方案整理成一个表格解法时间空间是否推荐理由暴力双层遍历O(m*n)O(1)不推荐效率太低只适合链表极短的玩具数据哈希集合O(mn)O(n)推荐用作第一版好写好懂但空间有开销长度差法O(mn)O(1)推荐直观代码略长双指针O(mn)O(1)强烈推荐优雅、简洁、面试加分4.3 一个容易被忽略的坑有环链表前面说了LeetCode原题默认链表无环。但面试官很可能追问一句如果两条链表各自可能有环呢这就变成了进阶题。有环情况下处理方法完全不同。标准套路是这样的第一步分别判断两条链表是否有环。方法就是快慢指针一个走两步、一个走一步如果会相遇说明有环并且还能找出入环点。 第二步如果两条链表都没有环就用上面任意一种常规解法。 第三步如果一条有环、一条无环直接返回不相交。 第四步如果两条都有环又分两种情况。一种是在入环之前就合并了那就用长度差法或双指针先找合并点但在处理时得注意避开环另一种是各走各的环那就分别找到入环点后看两个入环点是否在同一个环上如果不在同环说明不相交如果在同环交点可以是任一入环点。我建议一般面试场景下先把无环的常规解法讲清楚再提一句“如果链表有环可以先通过快慢指针找到入环点再分情况讨论”这就足够展示能力了。不用强行把有环的完整代码背下来除非候选人明确要求深入学习。5. 面试场景实战与避坑清单5.1 拿到这道题的正确思考顺序刷题和面试不一样面试时面试官更看重你的思考过程而不是你背了哪个模板。我建议拿到题目后按这个顺序组织思路第一步向面试官确认几个边界条件链表是否允许为空链表是否有环是否允许修改原链表结构这几句话能体现你的工程意识。第二步先给出最朴素的想法。可以说最粗暴的做法是固定A的每个节点依次遍历B的每个节点但这样是O(m*n)不太行。第三步提出用空间换时间的方案也就是哈希集合。在纸上画出两条链表标出交点说明先用set存A链节点再遍历B链命中第一个交集节点。这样做的时间是O(mn)额外空间是O(n)。第四步也是关键一步主动说我还能把空间优化到O(1)。这时引出双指针并口头解释两条指针走的路程相同最后必然在交点或null处相遇。这样下来面试官会看到你完整的问题解决链路暴力 - 时空权衡 - 最优解这比直接背出双指针代码要加分得多。5.2 我踩过的和见过别人踩的坑这部分是我最想写的内容。双指针解法代码很短但它坑人的地方也不少。第一个坑是“用值比较而不是引用比较”。我见过有人写出if (pA.val pB.val) return pA;这样的代码结果遇到值重复的测试用例就挂了。再次强调链表节点之间的相等必须用节点本体也就是pA pB因为只有地址相同才是真正共享。第二个坑是“跳转时机错误”。正确写法是当pA走到null后再跳转到headB。如果写成pA.next null时跳转就会少走最后一个节点导致总路程不对。这个bug很隐蔽单测几组数据可能都测不出来但遇到两条链表长度差比较大的例子就会出错。第三个坑是“忘记处理空链表”。虽然空链表时循环也能正常工作但最好在函数开头就明确判空返回null。这不只是为了正确性也是给面试官看的代码洁癖。另外有些编程语言里对null取属性会直接抛出异常提前判空是更稳妥的习惯。第四个坑是“只背代码不理解推导”。面试官如果让你解释“为什么双指针能够在交点相遇”你答不上来那就很尴尬。我见过不少候选人能默写出代码但一问原理就说“我看别人这么写的”。这种回答在面试中掉分很快。所以不管是为了面试还是为了真正提升技术上面3.2小节的数学推导一定要能自己讲一遍。第五个坑是“调试时犯了低级错误”。链表这种结构调试起来比数组麻烦因为它不是连续内存没法一目了然。我自己的习惯是在本地测试时给每个节点打上唯一标记或者用对象的id值作为区分这样才能清晰地看到pA和pB到底走的是哪条路。5.3 常见问题速查表我把这道题可能遇到的疑问集中成一个速查表平时复习时扫一眼就够了问题答案相交的判断依据是什么节点引用相等nodeA nodeB不是值相等两个链表都不为空但不相交双指针最终在null处相等返回null一个链表为空直接返回null两条链表完全相同交点就是头节点双指针第一轮就相遇要求空间O(1)用双指针法或长度差法链表有环怎么办先用快慢指针检测环再分四种情况讨论可以修改链表结构吗理论上可以但不推荐原题默认不允许修改双指针为什么不会无限循环因为双方总路程都是L1 L2最终同时到达null5.4 一个容易延伸出来的面试追问面试官如果对这道题比较满意大概率会顺带问一句“你还知道哪些双指针的链表题”。这时候如果你能列举出环形链表检测、删除链表倒数第N个节点、寻找链表中间节点就能展示出你确实掌握了这一类技巧而不是只会背一道题。我自己总结的规律是链表题里的双指针本质上是在控制“相对速度”或“相对路程差”。相交链表用到的是路程差环形链表用到的是速度差删除倒数第N个节点用到的是距离差。你看思路是同一个体系题却能变化出很多种。最后再分享一个小技巧本地练习时别只盯着LeetCode那个图形界面。你完全可以自己构造节点指针来做实验。比如Python里可以定义两个节点对象再把后一个节点的next指向前一个节点通过打印节点的id值来确认相交Java里可以打印System.identityHashCode(node)也能达到同样效果。手动推演两遍比看十篇题解都有用。这道题我刷了不止一遍每次做都还能发现一点新东西。双指针解法看着简单但能把其中的路程差原理讲到让人点头才算真正掌握了。如果你目前还在为链表题发愁不妨就从相交链表开始用它把节点的引用语义和双指针思路一次吃透。
