★ FEATURED ARTICLE 刷过算法题的同学多少都在链表题上栽过跟头。LeetCode 160「相交链表」就是这样一道看起来简单、上手才发现暗坑不断的题目——给你两个单链表 headA 和 headB要你找到第一个相交节点相交就返回节点不相交就返回 null。你可能会说这不就是比一比节点地址吗真到了面试现场能用双指针法把思路讲清楚的人远没有想象中多。更别提长度差法、哈希集合、栈解法、还有各种边界条件每一个点都可能是面试官深挖的方向。这篇文章我会从最直观的暴力解法讲起逐步演进到哈希集合、双指针法、长度差法再补充几个面试常考的变形问题和我自己踩过的实际坑。题的难度不算高但信息量其实很大值得静下心读一遍。1. 读懂题面相交的本质是同一个节点不是相同的值1.1 题目重述headA、headB 与 intersectVal 的含义先把这个题的实际输入输出说清楚。LeetCode 160 的入参是两个链表的头节点headA和headB如果它们从某个节点开始共享同一段节点就返回那个共享的起始节点如果没有共享段返回null。官方示例里给了这么一组链表A: 4 - 1 - 8 - 4 - 5 链表B: 5 - 0 - 1 - 8 - 4 - 5交点是值为8的那个节点。注意一个细节链表 B 里也有一个值为1的节点但这个1和链表 A 里的1并不是同一个节点只是值相同。真正的共享段从值为8的节点开始后面8 - 4 - 5完全是同一串节点。这里就引出了整道题最核心的一个概念判断相交必须看节点引用/地址是否相同而不是节点值是否相等。在 C/C 里是两个Node*指针相等在 Java/Python 里是同一个对象引用。这一点如果开始没跟面试官确认后面极容易写歪。1.2 节点相同与值相同的区别最容易翻车的地方值相同的节点可以同时存在在很多地方比如两条链表各自都有一个值为1的节点但它们之间没有任何关系。链表是链式结构节点在内存中的位置才是唯一身份标识。我见过不少人写出这样的判断逻辑if currentA.val currentB.val: return currentA这种写法在相交链表这道题上会直接误判。两条不相交但节点值完全相同的链表会被错误地认为相交了。反过来就算两条链表值序列一样只要节点地址不一样就不算相交。这个点也决定了后面所有解法的底层的比较逻辑双指针里的pA is pB、哈希集合里集合中存的是节点对象本身而不是节点的值。写代码时如果脑子里这个概念不清晰很容易写出值比较的版本。1.3 为什么 #160 值得反复刷考点与面试价值这道题被归为中等难度但它包含的考点非常密集第一是链表引用语义。能不能区分值和引用是很多面试官判断候选人基本功的试金石。第二是空间复杂度的优化思维。最直观的哈希解法需要 O(m) 额外空间能不能优化到 O(1)这种从哈希到双指针的推进路径在面试中比直接甩出最优解更能体现思考过程。第三是边界条件的敏感性。空链表、不相交但长度相同、不相交但长度不同、交点在头节点、交点在最尾部……每一类用例都能暴露出不同写法的隐患。第四是双指针思想的抽象能力。链表题里的双指针通常用来找中点、找倒数第几个节点、判环而 160 里的双指针思路是通过拼接两条链表来让两个指针走相同的路程这个模型在其他题目里也能迁移。所以这道题不是刷过就完而是值得你在面试前反复模拟讲演几遍。2. 暴力解到哈希集合先把能AC但不够优的路走通2.1 暴力枚举两层循环比对节点引用讲到解法我习惯先把最笨的方式摆出来。遍历链表 A 的每个节点再遍历整个链表 B看 A 的当前节点在不在 B 里def getIntersectionNode(headA, headB): pA headA while pA: pB headB while pB: if pA is pB: return pA pB pB.next pA pA.next return None时间复杂度 O(m*n)空间复杂度 O(1)。这个代码本身没有错误逻辑也对但在面试里最好只作为我首先想到的最直接方案口头提一下说明痛点一旦链表长到几万甚至几十万节点这个复杂度完全不可接受。不要真的埋头把两层循环写完面试官想看到的是你快速发现问题、并有优化方向。2.2 哈希集合空间换时间的直观解法暴力解法最浪费的地方在于每次判断都要完整遍历另一条链表。一个自然优化是把链表 A 的所有节点存到一个哈希集合里然后遍历链表 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)。这是非常标准、见效快的解法也是绝大多数人第一次能 AC 的版本。哈希集合法的优点在于思路直观、代码不容易出错很适合面试最开始热场。但它有一个明显的天花板需要额外存储链表 A 的全部节点空间成本高。如果链表有几十万个节点这个内存占用是能感知到的。2.3 面试时的桥段从哈希集合法自然引出 O(1) 空间我在面试指导时经常跟朋友说刷 160 这道题真正的加分项不是你写出了哈希解法而是你能接住下面这个追问能不能把空间复杂度降到 O(1)听到这个问题你心里应该立刻浮现出两个方向一个是长度差法先走完一遍数出两条链表的长度差让长链表指针先走差值的步数然后同步前进另一个是双指针法两个指针各自走完自己的链表后再切换到对方的链表上继续走。这两个方向都能做到时间 O(mn)、空间 O(1)。下面我分别讲清楚它们的原理和实现。面试官想听的不只是代码能跑而是你为什么这么设计的推理过程。3. 双指针法让两条链表在行程上等价交点自然浮现3.1 双指针法的完整流程双指针法的写法非常简洁核心逻辑就一个while循环def getIntersectionNode(headA, headB): if headA is None or headB is None: return None 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两个指针分别从 headA 和 headB 出发各自往前走。关键规则是当某个指针走到 null 时不从 null 继续而是跳到另一个链表的头节点继续走。loop 结束的条件是pA is pB它们相遇的位置就是交点如果一直不相遇最终它们会同时走到 null此时pA is pB也成立因为都是 null返回 null。这个代码乍看之下有一点魔术感尤其第一次接触的人会问凭什么它们就一定能相遇3.2 数学证明为什么总路程相同就一定能相遇我来做一遍完整的推导。设链表 A 的长度为 m链表 B 的长度为 n。设公共部分长度为 bA 的不相交部分长度为 aB 的不相交部分长度为 c那么m a b n c bpA 的行走路线是先从 headA 出发走完 A 的全部节点到达 null然后跳转到 headB再走 B 的不相交部分 c最终到达交点。那么 pA 走到交点的总步数是a b cpB 的行走路线完全对称走完 B 的全部节点到达 null然后跳转到 headA再走 A 的不相交部分 a最终到达交点。pB 走到交点的总步数是c b a两者相等。因为两个指针是同步移动的每一步都走一格所以当它们各自走了a b c步之后会同时到达交点。如果两条链表没有交点呢相当于b 0pA 从 A 走到 null再跳到 B 走到 nullpB 从 B 走到 null再跳到 A 走到 null。总步数都是a c两个指针会同时到达 null循环退出返回 null。这个证明非常关键面试时建议先给这个数学推导再贴代码。它展示了你不只是背了一个双指针模板而是真的理解为什么需要先走完自己的路再去走对方的路。3.3 从拼接链表视角理解两段路最后共享了同一条跑道我还想再给一个更直观的类比方便你现场讲给面试官听也方便自己记忆。把两条链表分别拼接成两条完全等长的新路径路径1链表A 接上 链表B 路径2链表B 接上 链表ApA 走路径1pB 走路径2。注意这两条路径的总长度都是m n完全一样。如果两个链表有一个公共段那么拼接后路径1 和路径2 的末尾部分一定是完全相同的公共段只是前面错开了。两个指针同步前进走过前导的错开区之后就会自然同时进入公共段并且第一次在同一位置的时刻就是交点的位置。这就像两个人在跑环形接力跑的圈数相同跑道后半段是共享的那么两个人必然会在共享道的某个位置碰头。没有共享道则两个人都跑完全程在终点null碰头。3.4 双指针代码实现的几个关键细节上面给的 Python 代码是最精简版本但写代码时有几个细节需要注意。第一条件判断用is而不是。这题里节点比较应该是对象引用比较Python 里用is最准确。如果你用在 LeetCode 环境里因为 ListNode 默认没有重写__eq__所以结果上可能也对但语义上不够严谨。在面试里主动说出这是引用比较所以用is会显得你很注意细节。第二指针切链表头的操作要放在已经走到 null的时刻而不是倒数第二个节点时。我见过有人这样写# 错误示范 pA pA.next if pA.next else headB这会在最后一个节点处提前跳转完全跳过 null破坏了两条路径等长的关系。特别是两条链表不相交时这种写法可能造成死循环。正确做法是pA pA.next if pA else headB当 pA 已经为空时才跳到 headB。C 版本也类似ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { if (!headA || !headB) return nullptr; ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }第三刚开始可以加一个空链表判断。如果任意一个链表为空直接返回 null。不加这个判断其实也能跑因为循环只有在两个指针相等时退出其中一个为空时它们不等会继续跳转但提前判断能让代码意图更清楚还能少执行几轮循环。3.5 边界条件逐个验证光有代码还不够我会在头脑里把各种用例过一遍避免翻车交点在链表中部正常情况pA 和 pB 在交点相遇。交点在头部headA 就是 headB循环一开始pA is pB成立直接返回头节点。交点在最尾部两条链表直到最后一个节点才共享双指针也能走到。不相交且长度相同两指针同步走到各自的最后一个节点然后再走一步同时到 null退出返回 null。不相交且长度不同pA 先到 null 跳到 headBpB 后到 null 跳到 headA最后同时到 null返回 null。一个链表为空直接返回 null。这些边界用例自己在脑子里过一遍比刷十道同类题都管用。4. 长度差法先量出差距再让两个指针同步出发4.1 长度差法的核心逻辑与实现如果说双指针法是用路线设计解决问题那长度差法就是用几何对齐解决问题。思路更直白两条链表如果相交那么它们从交点到末尾的公共段长度一定相同。既然如此我只要让两个指针从距离末尾相同的位置开始同步走就一定能同时到达交点。怎么做到距离末尾相同先把两条链表的长度都数出来。设长度分别为lenA和lenB。如果lenA lenB就让 A 的指针先走lenA - lenB步反之让 B 的指针先走lenB - lenA步。这样两个指针剩余到末尾的距离就一样了再一起步进逐个比对是否指向同一个节点。def getIntersectionNode(headA, headB): lenA, lenB 0, 0 pA headA while pA: lenA 1 pA pA.next pB headB 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两个主循环加起来是 O(mn)后面对齐查找也是 O(mn)总复杂度同样 O(mn)空间 O(1)。4.2 双指针法与长度差法的对比与取舍既然两种方法复杂度一样面试时选哪个更好我的看法是分情况。如果你是第一次接触这道题长度差法更容易理解。它不需要跳转到对方链表这种稍微绕一圈的思维纯粹靠数长度—对齐—同步走三步走代码直观不容易给别人解释时卡壳。现场写代码时也不容易因为跳转逻辑而写错。但双指针法在实际代码实现上更简洁。它只需要一个循环没有预先数两边长度的额外遍历也不用先算差值再走 for 循环。虽然两者都是 O(mn)但双指针法的常数项更小代码量更少看起来更优雅。还有一个细节值得注意长度差法需要先完整遍历两次链表来数长度然后再从头走一遍。也就是总共可能遍历常量次而双指针法每个指针从各自头节点出发最多各走mn步整体上少了一次从长度差开始同步前进的冗余。严格来说常数性能略优。面试官通常都能接受这两种解法。我的建议是开头讲长度差法因为好理解然后补一句如果进一步优化可以用双指针法把两条链表拼接起来让两个指针走相同的总路程——这样既展示了你的思路广度又给了最优解。5. 进阶变形和面试官最爱追问的四个方向5.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这个变形能很自然地体现你对链表结构的理解——交点和尾部是强关联的。有些面试官会把这个作为对 160 的追问看你会不会从找交点切换到只需要布尔判断。5.2 链表带环考察难度瞬间升级如果两条链表本身可能存在环相交问题会变得复杂得多。原因在于走到底这个操作不再可靠因为可能永远走不到 null。这时候最稳妥的思路是用哈希集合兜底给每个访问过的节点做好标记遍历链表 A直到遇到 null 或遇到重复节点说明有环时停止再遍历链表 B同样直到 null 或重复节点为止期间只要某个节点出现在 A 的集合里就是交点。这个方案的复杂度和判断是否有环紧密相关面试时只要你能指出带环会让尾节点相同这种推论失效并且能给出哈希解决的思路面试官一般就会满意。追求 O(1) 空间解决带环相交的完整推导非常繁琐除非对方明确考到否则不建议在面试里现场硬推。5.3 栈解法与 Floyd 判圈法思路拓展除了上面四种解法还有两种思路值得了解虽然不是最优解但能展示你知识面广。栈解法的思路是把链表 A 的节点依次压入栈链表 B 的节点也压入另一个栈。然后两个栈同时弹出最后一个相同的节点就是交点。原理很简单因为两条链表的公共段都在尾部从尾部往前看公共段是完全重合的。时间 O(mn)空间 O(mn)适合口述不适合作为最终答案。Floyd 判圈法则是另一种脑洞把链表 A 的尾节点接到链表 B 的某个节点或链表 B 的头上构造出一个环然后用快慢指针找到环的入口。这个入口本质上就是相交点。但这个方案会修改链表结构使用前要确认是否允许而且最后必须把结构还原稍有不慎还会破坏原来的链表。一般情况下我只会作为extra idea在最后提一句不会作为主推方案。5.4 多语言实现里的引用比较细节最后提醒一下不同语言中节点比较的写法差异。Python 用is not pB作为循环条件集合里直接存节点对象即可。如果担心自定义类覆盖了__eq__和__hash__也可以存id(node)判断时用id(node) in seen但可读性稍差一些。Java 里两个对象默认用比较的就是引用所以pA ! pB是对的HashSet 里直接存 ListNode 对象内部调用 hashCode 和 equals但默认实现都基于对象地址一般不会出问题。如果面试官较真可以提醒一句假设 ListNode 没有重写 equals/hashCode。C 直接用指针比较pA ! pB判断的是两个Node*是否指向同一块内存天然符合题目要求哈希表方案用unordered_setListNode*也没问题。Go 和 Rust 的指针比较也类似但 Go 里注意用reflect.DeepEqual或者直接指针Rust 里则常用std::ptr::eq。这些边界工程里见过太多因为比较语义不清导致的 bug 了。6. 现场答题的节奏和我实际踩过的坑6.1 推荐的现场答题流程如果你只有十分钟来做这道题我的建议是分四步走第一步确认语义。先问面试官这里的相交是指节点引用相同而不是值相同对吗这个确认是你后续所有判断的基石也能证明你习惯先澄清需求。第二步快速给出哈希解法。花一两分钟说明遍历 A 存集合、遍历 B 查集合复杂度 O(mn)、O(m)用这个解法确保基础分拿到。第三步主动提出优化方向。自己追问自己能不能O(1)空间然后引出双指针法。重点把拼接路径、总路程相同的思路讲清楚顺便把不相交时同时到 null 的情况也讲明白。这部分是加分核心。第四步在代码里显式处理边界条件。写完代码之后主动说出你要验证的用例相交在中部、相交在尾部、不相交且长度不同、空链表。想清楚这些再提交面试官对你的评价会高很多。6.2 我刷题和面试中踩过的实际坑第一次刷这道题时我用的是哈希解法AC 之后就没有再去管空间复杂度。之后面试问我能不能O(1)空间当场我尝试写双指针结果写成了用pA.next判空跳转的版本正好踩了上面说的提前跳转导致死循环的坑。当时为了演示边界情况还在白板上画了半天没画明白。那次之后我才把走到 null 再跳转这个细节刻进脑子里。还有一个很实际的坑长度差法里我一开始没有把pA和pB重新指向 headA 和 headB而是直接用已经走到 null 的指针继续走。结果自然是 null 指针异常。后来我养成一个习惯凡是修改了指针位置的算法代码里都加上一行注释告诉自己这里开始指针要回到原点重新走。6.3 一套可以直接拿去用的测试用例清单最后给你一套我每次复习必过一遍的用例直接拿来检查自己的代码场景链表A链表B期望输出交点在中部4 - 1 - 8 - 4 - 55 - 0 - 1 - 8 - 4 - 5值为8的节点交点在头部3 - 2 - 1同左同一头值为3的节点交点在最尾部6 - 79 - 7值为7的节点不相交且长度相同1 - 2 - 34 - 5 - 6null不相交且长度不同1 - 2 - 3 - 45 - 6null值相同但节点不同1 - 1 - 11 - 1 - 1null一条链表为空null1 - 2null两条链表都为空nullnullnull其中值相同但节点不同这一条最容易暴露用值比较的错误实现值得多花点时间琢磨。我的经验是链表类算法题真正拉开差距的往往不是主流程而是这些边界处理。你花十分钟把双指针的数学证明和边界条件理顺了后面遇到任何链表相交的变体题都会从容得多。
阅读完成 · 觉得有帮助？
