企业官网建设流程全解析

相交链表这道题，我在LeetCode上刷到过，也在面试中被人问过。它看起来平平无奇——给你两个链表，找出它们相交的起始节点——但真到写代码的时候，不少人会卡住。还有更多人虽然能写出那个经典的双指针解法，但你要是追问一句"为什么两个指针走完一条链表再走另一条，就一定能碰上"，他又说不清楚了。

这篇文章我打算把这题的来龙去脉完整拆一遍，从最简单的暴力思路讲到最优解，再讲清楚那些网上资料通常一笔带过的原理细节。无论你是刚接触链表的新手，还是准备面试想把这题聊透的选手，这篇都应该对你有帮助。

1. 先从题目本身说起：相交到底在说什么

很多人在相交链表这题上犯的第一个错，不是代码写错，而是没理解题目里"相交"的精确含义。

题目给的描述大致是：编写一个程序，找到两个单链表相交的起始节点。下面通常会跟一张图，画着两个链表在一个节点之后合并成同一条链表，整体呈Y字形。注意这个形状——是Y，不是X。

为什么不会是X？因为这是单链表，每个节点只有一个next指针。如果一个链表真的呈X形，意味着某个节点有两个不同的后继，这在单链表结构里根本不可能存在。所以两个链表一旦相交，从交点开始，后面所有节点都是共用的，一直到链表结束。

我在学习的时候吃过一个亏，一开始用"节点的值相等"来判断相交，跑测试样例发现错得离谱。链表节点A的值是1，节点B的值也是1，但它们是完全独立的两个节点。判断相交要比较的是节点的引用——也就是节点在内存中的地址，而不是节点存储的值。只不过在刷题平台上，可视化测试用例会直接把相交部分共用，而我们写代码时要用a is b（或者C++里的a == b，指针相等）去判断，才会得到正确结果。

这题的进阶要求也值得一提：你能否在O(n)时间复杂度、O(1)空间复杂度内解决？也就是说，只能遍历有限的次数，并且不能用额外的哈希表、数组或者集合来存节点。这个要求直接堵死了"把所有节点存下来再逐个比较"这条简单路线，逼迫你去找更巧妙的办法。

从面试的角度看，这道题测的东西很精准：链表的基本操作、复杂度的分析能力，以及最重要的一点——能不能从两个链表的几何关系里看出隐藏的"对齐"思路。它不涉及复杂的算法范式（没有动态规划，没有贪心策略），考察的全是基本功和观察力。这也是为什么很多面试官喜欢用它来做"热身题"——你觉得简单，但简单题最容易暴露你有没有真正理解数据结构。

2. 我先用最笨的办法跑了一遍：暴力解法的价值

我第一次做这题，思路非常直接：拿链表A的每一个节点，去链表B里从头到尾找一遍，看有没有哪个节点和它引用相同。翻译成代码：

def getIntersectionNode(headA, headB): while headA: p = headB while p: if headA is p: return headA p = p.next headA = headA.next return None

这个解法正确吗？正确。能过测试吗？能，如果链表不长的话。但它有两个很大的问题。

第一是时间复杂度。假设链表A有m个节点，链表B有n个节点，外层循环要跑m次，内层循环每次要跑n次，整体是O(m*n)。一旦两个链表长度都到几千或几万，这个解法会慢到让人怀疑是不是死循环了。

第二是它完全浪费了一个重要信息：两个链表相交之后的所有节点是完全相同的。也就是说，如果我们能确定两个链表从某个位置开始重合，那么交点之前的部分长度差是可以算出来的。暴力解法根本没有利用这个几何性质，它只是盲目地全量查找。

不过我得说句公道话，暴力解法并不是毫无价值。我在很多实战场合都发现，拿到一道题先写一个朴素但正确的解法，能帮你确认自己对题意的理解是对的。尤其是链表这种数据结构，边界条件多（空链表、只有一个节点、头节点就是交点等等），一个朴素解法可以快速帮你把测试用例跑通，再来优化的时候，至少你有一个"正确版本"作为参照，不至于在优化过程中把逻辑改错。

暴力解法还有一个作用，就是让你真切体会到优化的必要性。当你的解法被判超时，你再去学双指针解法，会有一种"原来如此"的顿悟感。如果你一上来直接背最优解代码，很容易陷入"会写但不懂"的状态，面试的时候最怕这种情况——面试官多问一句"为什么"，你就露馅了。

顺着暴力解法往下想，很自然会想到一个优化：如果先把一个链表的所有节点存进哈希表，再遍历另一个链表去哈希表里查，不是省掉了一层循环吗？

def getIntersectionNode(headA, headB): seen = set() while headA: seen.add(headA) headA = headA.next while headB: if headB in seen: return headB headB = headB.next return None

哈希表解法的时间复杂度可以降到O(m+n)，空间复杂度则是O(m)或O(n)（取决于你把哪个链表装进集合）。这个解法在LeetCode上完全能通过，而且代码写起来几乎不可能出错。但题目要求的O(1)空间复杂度，它满足不了。如果你在面试中直接甩出这个解法，很容易被追问一句"能不能不用额外空间？"——这其实就是引导你往双指针方向想。

有意思的是，哈希表解法虽然不符合进阶要求，但你真去面试的时候，先说出哈希表解法、再沿着"如何去掉这个set"的思路推出双指针解法，会让面试官觉得你的思路是从约束条件里自然生长出来的，而不是背了模板。所以我建议你两个解法都掌握，理解它们各自的取舍。

3. 双指针解法的两个理解视角：对不齐的长度该怎么处理

现在来到重头戏：双指针解法。网上流传的版本长这样：

def getIntersectionNode(headA, headB): 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

非常短，短到让人怀疑这题是不是就这么简单。但如果你只是想把这行代码背下来，下次遇到可能还是不会做。我接下来用两个不同的视角来解释这个解法，都是我实际复盘时用过的思路，你可以挑一个更好接受的理解方式。

3.1 视角一：先算长度差，再同步前进

两个链表相交的特征是什么？是相交部分完全共用。那在相交之前的部分呢？两段是彼此独立的。

假设链表A在交点之前的长度为a，链表B在交点之前的长度为b，相交部分的长度为c。注意，a和b不一定相等，这恰恰是问题的难点——如果a等于b，那我们只需要两个指针从两个链表头部同步往前走，走一步比一次，第一个相等的节点就是交点。可现实往往是a不等于b，同步走的话，两个指针永远踩在不同的位置上。

怎么解决？核心思路是：让两个指针在距离链表末尾相同距离的位置开始同步走。

如果先遍历一遍两个链表，把长度分别算出来（假设是m和n），那么长链表上的指针就要先走 |m-n| 步，把长度差抹平，之后两个指针再同步前进，第一个碰面的节点就是交点。这个思路很直观，实现起来也不难：

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 is not pB: pA = pA.next pB = pB.next return pA

这段代码的正确性很容易验证。它先算长度，再对齐，然后同步走。为什么这种方法一定有效？因为两个指针一旦处在"距离链表末尾相同距离"的位置上，它们之后走过的路径长度完全一致。如果链表相交，那么在交点处它们会同时到达；如果链表不相交，它们会同时走到两个链表的末尾（都是None），循环结束时pA是None，返回None。

我用这个思路给一个朋友讲过这道题，他的反应是："这不就完了吗？为什么会有人觉得这题难？"确实，长度差思路不难，写起来也顺。那为什么双指针解法更出名？因为上述代码需要先遍历两遍链表计算长度，总共要跑两趟；而双指针解法只需要一趟逻辑上的遍历，代码还更短。更重要的是，双指针解法里藏着一个极聪明的"自动对齐"机制，理解了它，你会觉得这个解法是真的巧妙。

3.2 视角二：走完自己再走对方，本质是路程补偿

双指针解法的核心就一句话：每个指针都走一条"拼接路"——完整走完链表A，再走链表B；另一个指针则完整走完链表B，再走链表A。

你可能会问：这为什么能对齐？

我来推算一下。指针pA的完整路程是：链表A的所有节点数 + 链表B的所有节点数，也就是m+n。指针pB的完整路程是：链表B的所有节点数 + 链表A的所有节点数，也就是n+m。看，这两个数字是相等的。

"路程相等"有什么用？我们换一个角度来想。在上一篇的长度差思路里，我们是人为计算长度差来对齐；而在这里，两个指针各自走完整条列表的组合路程，等于两个人分别跑了完全相同的总距离。

更重要的一点是：两个指针在各自路程中的相对位置，始终存在某种对应关系。我不喜欢用"总路程相同"来解释，因为初看之下，你并不知道交点到底在路程的哪个位置。我想分享一个更形象的比喻：两个人赛跑，其中一个人先跑了一段（相当于链表A比链表B长），然后让两个人都跑"全程+m"或"全程+n"，最终他们会在某一段赛道上同时到达同一个地点——这个地点在最坏情况下是终点（None），在一般情况下的第一个重叠点就是交点。

如果你学过一些概率或者组合，可以把这想象成两个不同长度的链，各自接上对方的"尾巴"，变成两条等长的链。既然两条新链一样长，那么从各自头部出发的两个指针，每走一步都处于"距离新链末尾相同的距离"的位置。而由于两条新链的后半段（对应在原链表里相交的部分）是完全一样的节点，所以在某个节点上，两个指针一定会踩到同一个对象。

我第一次理解这个解法的时候，不是通过数学推导，而是真的在纸上画了两个长短不同的链表，然后在第二个链表后面接上第一个链表、在第一个链表后面接上第二个链表，画完就明白了。你也可以试试这个办法——画图永远比背结论有效。

沿着这个思路再看代码，还有一个隐藏得很深、但很关键的细节：两个指针同时到达None，也是一种"相遇"。如果没有交点，pA走完A再走B到最后，pB走完B再走A到最后，二者都变成None。此时pA is not pB为假，循环结束，返回pA（也就是None）。所以这个解法天然就处理了"不相交"的情况，不需要额外写判断。

4. 双指针解法代码实现与边界条件：别在这些地方翻车

代码虽然短，但我在实际写的时候发现有两个地方特别容易写错，一个是循环条件，另一个是空指针的判断方式。

先看循环条件。很多版本会写while pA != pB:，这没问题，但在Python里需要注意：链表节点本身没有定义__eq__方法时，==比较的就是引用，所以pA != pB本质上也是在比较引用。不过为了语义清晰，我建议直接用is not，明确告诉读者我们比较的是"是否是同一个对象"。

第二个容易踩的坑是跳转语句的写法。看这段代码：

pA = pA.next if pA else headB pB = pB.next if pB else headA

这里我用的是if pA而不是if pA.next。为什么？因为如果pA已经走到链表末尾（pA是None），你还去访问pA.next，会直接抛出AttributeError: 'NoneType' object has no attribute 'next'。这个错误我至少犯过两次，都是因为脑子里想着"走完了就跳转，那应该是pA.next为空时跳转"，结果忘了先判断pA本身是否为None。

正确理解是：当pA是None时，说明它已经走完了当前链表，该切换到另一个链表了。所以判断条件得是if pA，而不是if pA.next。

还有一种更直观的写法是先判断再移动：

while pA is not pB: if pA is None: pA = headB else: pA = pA.next if pB is None: pB = headA else: pB = pB.next return pA

这种写法和前面的三目运算符版本是完全等价的，但读起来更不容易出错。如果你是在面试现场手写代码，我建议你用这种拆开写的版本，因为面试官更看重你思路是否清晰，而不是代码是否足够精简。

然后我们来看边界条件的处理。

• 空链表：如果headA或headB是None，代码会怎么走？第一轮循环判断pA is not pB，此时一个是None一个是某个节点，条件成立；进入循环后，pA为None则跳转到headB（也是None），pB则继续走。最终两个指针中会有一个先耗尽路程变成None，另一个也很快变成None，循环结束返回None。整个过程不会崩，但为了效率，你也可以在一开始就加一行提前判断：

if not headA or not headB: return None

这行其实并不是必须的，但写上也挺稳妥，特别是你在和面试官讲解的时候，主动提一句"空链表直接返回None"，会给对方留下考虑周全的印象。

• 两个链表从第一个节点就相交：此时headA就是headB，第一轮循环条件pA is not pB直接不成立，返回headA。代码不出错，但如果你在循环里先移动指针再判断，就会错过去，所以注意循环条件的判断时机。

• 链表中只有一个节点且不相交：比如A是[1]，B是[2]。pA走完A之后跳到B的开头，pB走完B之后跳到A的开头，再次经过一轮，两个指针同时变成None，返回None。这个过程中两个指针永远不会指向同一个非空节点——因为根本没有交点。

还有一个我自己做测试时发现的坑：如果你用while pA and pB:之类的条件去循环，会导致部分相交情况提前退出。最安全的写法就是老老实实按pA is not pB来，别自作聪明加其他条件。

拿Python写完之后，我顺手也用C++写了一遍，核心逻辑完全一样，只是把is not换成了!=，把None换成了nullptr。如果你面的是C++岗位，建议把这段也练熟，因为C++里面指针的用法比Python更贴近内存模型，写起来思路会更顺。

5. 哈希表解法：空间换时间的备选方案与面试话术

虽然双指针解法是这道题最优解，但我觉得哈希表解法仍然值得好好讲讲。原因有两个：第一，它是一种非常通用的解法思路，链表题的"找重复/找交点"类问题里经常用到；第二，面试的时候，先讲哈希表再优化到双指针，这种"从直白到巧妙"的推进过程，本身就是一种很好的答题策略。

哈希表解法的代码前面已经给过了，核心就两步：把链表A的所有节点放进一个集合，然后遍历链表B，逐个检查当前节点是否在集合中。第一个在集合中出现的B节点就是交点；如果遍历完B都没遇到，说明两个链表不相交。

它的时间复杂度是O(m+n)，空间复杂度O(m)（如果存A的话）。有人会问：为什么空间复杂度是O(m)而不是O(m+n)？因为集合里只存了其中一个链表的所有节点。你要是较真的话，也可以说O(m)或者O(n)取决于你存的是哪个，通常取较大的那个。

这个解法相比双指针的优点是：思路直白，不易出错，特别适合在面试一开始快速给出一个可行方案。你甚至可以主动说明："这是用空间换时间，不符合O(1)空间的进阶要求，那我们能不能不用额外空间呢？"——这句话就像抛出一块砖头，顺着"去掉哈希表"这个念头，就引出了双指针解法。

在实际刷题过程中，我见过不少新手一上来就追求最优解，花半小时憋不出代码，最后一看答案，发现最优解就五行。我的建议是反过来：先写一个必然正确的暴力解法或哈希表解法，拿到通过的结果之后，再思考怎么优化。这样至少保证了"能做出来"，而"能优化"是在"能做出来"的基础上讨论的。面试也一样，面试官期待看到的是一种逐步改进的过程，而不是你背一段最优解背得行云流水。

前面提到过一种错误的比较方式：用节点的值去判断相交。在这道题里这种错误比较明显，因为测试用例可能有多个值相同的节点，导致你的哈希表里存了一堆节点，却永远找不到真正的交点。这个概念同样适用于哈希表解法：必须把节点对象本身存进集合，而不是节点的值。Python里哈希需要一个可哈希的对象，链表节点（默认的object）天然是可哈希的，所以可以直接存。如果你用自己的类定义，注意别把__hash__给覆盖掉了，否则会出现意想不到的行为。

最后补充一个关于哈希表解法的真实场景。LeetCode上这道题有一个隐藏的坑：如果你在本地IDE跑通了一个正确的解法，但直接复制到LeetCode提交，可能会因为类名或者方法名不一致而报错。我遇到过几次这种情况，结论是：刷题平台的模板代码一般定义了ListNode和Solution，你只需要在类里实现getIntersectionNode方法即可。哈希表解法也不例外，测试时会用两个链表的头节点调用你的方法，内部怎么实现平台不关心，它只看返回值。

6. 做题过程中我需要重点避开的几个坑

题目本身不难，但"看着不难"恰恰是容易翻车的地方。我在反复做这题的过程中，整理出了一批高频错误，每一个都是我或者身边朋友亲自踩过的。我把它们列在这里，你们刷题的时候可以对照着自查。

第一个坑：用==而不是is。在Python里，两个不同的对象即使内容完全一样，==也不一定返回True——这取决于这个类有没有实现__eq__。链表节点类在LeetCode的原生定义里通常没有实现__eq__，所以==和is在大多数情况下行为相同。但你不能依赖这个"大多数情况"，尤其到了别的语言里情况又不一样了。C++里，指针比较就是用==，因为两个指针指向同一块内存地址时它们相等。Java里则要小心，程序员习惯用==比较基本类型，但比较对象时==比较的是引用是否相等，这恰恰是我们想要的，可有的同学会条件反射写成.equals()，那就错了——.equals()默认比较引用没错，但如果你Override过equals，就会变成比较内容。我建议你在刷题时明确自己在用什么语言，遵循该语言的比较习惯。

第二个坑：忽略"不相交也要返回None"。有的解法在写完双指针之后想着"万一它们不相交就会死循环"而加了很多奇怪的判断，其实没必要。双指针解法自带处理不相交情况的机制——两个指针最终同时变成None。这个机制我在前面已经详细说明过了。如果你在循环里加了额外的计数器、或者用while pA and pB之类的条件，反而可能出错。

第三个坑：尝试修改链表的指向来标记路径。我见过有人提出这样的思路：先遍历链表A，把每个节点的next指向自身或者指向一个特殊节点，然后再遍历B，遇到标记过的节点就是交点。这个思路在部分题目里可以用，但在这题里有两个问题：一是空间复杂度可能不达标，二是修改了链表结构，可能破坏后面的测试用例。题目只要求返回相交节点，并没有允许你修改链表。面试的时候如果你提出这个思路，面试官可能会顺着问"那如果要求不修改链表呢"，你要是答不上来反而减分。

第四个坑：假定两个链表一样长。我见过不少初学者一看到这题就写：

while headA and headB: if headA is headB: return headA headA = headA.next headB = headB.next

这个代码在两个链表长度相同时是对的，但长度一不等就漏掉交点。原因是两个指针没能"对齐"。这恰好就是双指针解法要解决的核心问题。如果你写出来这个版本，一定要意识到"长度可能不同"这个前提，否则测试用例会给你狠狠上一课。

第五个坑：不考虑空链表。前面说过，双指针代码对空链表也能正常工作，但你可以加上提前判断来提升可读性。哈希表解法里，如果headA本身是None，while headB:循环可能根本不会执行，然后你返回None——也是对的。所以这类边界条件更多是"锦上添花"，而不是"救命稻草"。但我还是建议你在做题时主动想一想空链表的情况，因为面试官真的会问。

这些坑归纳起来，其实反映了一个共性：链表题目里，"指针"是你的核心武器，而"空值"是最常见的敌人。任何一次next操作之前，都值得想一想，当前这个节点是不是已经是None。一次is not比较之前，想想它是不是永远为True。凡是能让代码更防御性的写法，面试时都可以主动加上。

7. 从相交链表延伸到一类问题：链表题里的"相遇"套路

做题有个习惯我坚持了很久：一道题做完之后，试着把它和以前做过的题建立联系。相交链表这道题看起来独立，实际上它和另外几道经典链表题共享着同一个解题内核——"两个指针在链表上移动，直到满足某个条件"。

第一类相关题是环形链表。给你一个链表，判断有没有环。经典解法是快慢指针：快指针每次走两步，慢指针每次走一步，如果链表有环，两者必定在环内相遇；如果没有环，快指针会先到达None。这个题和相交链表的双指针解法有什么关系？表面上没直接关系，但如果你深入思考一下，它们都在利用"路程差"或"周期性"来构造必然会发生的事件——一个有环则必相遇，一个相交则必相遇。做多了你会发现，链表题的很多精妙解法都建立在"任何两个指针在满足某些条件后一定会碰面"的洞见上。

第二类相关题是找环形链表的入口。LeetCode上有一道题要求在O(1)空间下找到环的入口节点。解法先是用快慢指针找到相遇点，然后再用两个指针从头开始走，最后在入口处相遇。这个解法里也藏着一个复杂的数学推导，需要你理解两个指针在环内相遇时，已经走过的路程之间存在某种倍数关系。相比之下，相交链表的核心要简单得多——两个指针走的总路程相等，然后就自然对齐了。

第三类相关题是合并两个有序链表。这个题看起来和相交没什么关系，但我常拿来和相交链表做对比：合并两个有序链表需要同时遍历两个链表，比较当前节点值的大小，然后选择更小的那个节点接到结果链上。它和相交链表有一个共同的考点：当两个链表长度不一致时，你需要小心处理"其中一个链表已经走完，但另一个还没走完"的情况。这种"非对称遍历"的节奏感，做多了以后会觉得特别熟悉。

我在这里把这些题串起来，是想表达一个观点：刷题不能只刷"怎么做"，还要关注"为什么这么做"。相交链表的最优解，表面上是"走完A走B，走完B走A"的口诀，实质上是对"路程补偿"概念的一次展示。你要是在面试中能把这个概念讲清楚，面试官对你的评价会明显好于只会背代码的人。

还有一种更实用的做法：每做完一道链表题，就自己改编一下。比如把"两个链表"改成"三个链表找交点"，或者把"单链表"改成"双向链表"，看看解法会怎么变。这样做的收益不是立竿见影的，但长期积累下来，你对链表结构的直觉会灵敏很多。我认识的几位算法水平很高的朋友，都是用这种"改题训练"的方式保持状态的。

8. 想通之后，这道题就真的简单了

最后我再多聊一点个人感受，算是我刷了几百道题之后对这些"简单题"的看法。

相交链表这道题，我第一次做出正确解法的时候，用的是先算长度再对齐的思路。代码写了三十多行，跑通了，我还挺有成就感。后来看到双指针解法的五行业代码，第一反应是什么？是"这也太短了"，第二反应是"它凭什么能保证相遇？"我花了不少时间画图、推导、举例子，才彻底接受了这个解法。这个过程让我意识到，算法题的"理解"和"看懂"是两回事。看懂只需要顺着别人的思路走一遍，理解则需要你能够在没有提示的情况下，自己推到这个解法。

所以我建议你，不管用什么方式学习这道题，最后都停下来做一件小事：不看任何资料，自己独立推导一遍双指针解法相遇的证明。写不出来也没关系，卡住了再看，看完再继续推。这个过程重复两三遍，这道题在你心里就真正"长住了"。

还有一个小技巧可以分享给你。面试的时候如果被问到这道题，你可以在讲完双指针解法之后，主动提一句"如果不相交，两个指针最终会同时到达链表的末尾null，所以循环自然结束"。这句话听起来像在补充边界条件，实际上是在向面试官展示你不仅知道解法，还理解了解法为什么会收敛。我见过不少候选人能在白板上默写出双指针代码，但一被问"如果它们没有交点会发生什么"就卡壳。你要是能轻松回答这个问题，这轮的印象分会高不少。

如果你想把这道题纳入复习体系，我建议把它和环形链表、合并两个有序链表放到同一天做。三个题一起做，你会发现它们之间有一条隐隐相连的线：都是链表上的指针运动问题，都在考你怎么处理"遍历完一条链去另一条"的状态切换。把这些题目放在一起嚼透，比单独刷十道不相关的题更有价值。

我自己每次做链表题，都会提醒自己一句话：链表题的难点往往不在于你懂多少数据结构和算法，而在于你能不能把一个朴素的想法，通过巧妙的指针操作变成高效代码。相交链表这道题，就是这种思维转变最好的入门教材之一。