1. 这道题为什么总在面试里反复出现单链表相交判断这个问题我在过去几年帮人做模拟面试、整理题库的过程中见过的出场频率高得离谱。它不像反转链表那样一眼就能写出代码也不像快慢指针找环那样有固定套路它卡在一个很微妙的位置思路谁都能说两句但真正动手写边界条件能把人绕晕。先说清楚这道题到底在问什么。给定两个单链表的头指针判断它们是否相交。所谓相交不是指节点的值相等而是指两个链表从某个节点开始物理上是同一个节点也就是内存地址相同。如果相交还要找出第一个公共节点也就是交点。这个定义本身就藏着第一个坑。很多人第一反应是遍历两个链表看有没有值相同的节点这个思路从根上就错了。两个链表完全可能拥有值相同的独立节点但它们并不相交。反过来相交的两个链表从交点开始到尾部所有节点的值和地址都完全一致因为那就是同一段链表。为什么面试官偏爱这道题我的观察是它一次性考察了好几个维度的能力对链表物理结构的理解、空间复杂度的敏感度、边界情况的处理、以及能不能从暴力解法一步步优化到最优解。一道题能筛出这么多信息性价比太高了。这道题适合谁看如果你正在准备技术面试链表这块还没彻底吃透那这篇内容值得你从头到尾跟着走一遍。如果你已经工作几年想重新梳理一下基础数据结构的手感也可以当复习。我会从最朴素的思路讲起一步步推到最优解中间把每个选择的理由、每个坑的成因都掰开说。提示本文所有代码以单链表为标准模型节点结构只包含一个数据域和一个 next 指针。如果你的场景是双向链表或带环链表处理方式会不同后面会单独提。2. 先把相交这件事的物理图景建立起来2.1 值相等和节点相同是两码事我见过太多人在白板上画两个链表节点里写数字然后指着两个都写着 7 的节点说这里相交了。这是最典型的认知偏差。链表相交的判定标准只有一个两个指针指向的是同一块内存。用生活化的类比来说两个链表就像两条路。值相等只是说两条路上都有一家叫7号的店但它们是两家不同的店。而相交是说两条路从某个路口开始合并成了同一条路之后走的是完全相同的路面。这个区别决定了整个算法的走向。如果我们只比较值那最坏情况下要两两比较所有节点复杂度爆炸且逻辑上就是错的。只有抓住同一节点这个本质才能用地址比较来判定。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next # 判断相交时比较的是 node1 is node2 # 而不是 node1.val node2.val2.2 相交之后为什么一定是 Y 字形而不是 X 字形这是另一个必须想清楚的点。单链表每个节点只有一个 next 指针也就是说一个节点只能有一个后继。如果两个链表相交那么从交点开始它们共享同一段尾部。这意味着两个链表一旦相交就再也不会分开。所以相交的形状必然是 Y 字形两条独立的链从上方下来在某个节点汇合然后共用一条尾巴。绝对不可能是 X 字形因为 X 意味着交点之后又分叉那就要求交点节点有两个不同的 next这违反单链表的定义。理解这一点非常关键它直接推导出一个重要结论如果两个链表相交那么它们的尾节点一定是同一个节点。这个结论是后面好几个解法的基石。2.3 长度差是绕不开的核心变量既然相交后共享尾部那么两个链表从各自头节点到交点的距离就可能不同。设链表 A 头到交点距离为 a链表 B 头到交点距离为 b公共尾部长度为 c。那么 A 的总长是 acB 的总长是 bc。两个链表长度之差就是 a-b 的绝对值。这个差值就是很多解法的突破口。比如让长的那个先走差值步然后两个指针同步前进它们就会同时到达交点。这个思路后面会详细展开。我个人的经验是面试时先把这三个图景在纸上画出来Y 字形结构、尾节点相同、长度差。画完这三个解题思路基本就浮出水面了面试官也会觉得你思路清晰。3. 从暴力解法到最优解的完整推演3.1 最朴素的暴力法双重循环拿到题最先能想到的就是拿链表 A 的每个节点去链表 B 里从头扫一遍看能不能找到同一个节点。def get_intersection_brute(headA, headB): if not headA or not headB: return None 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)m 和 n 分别是两个链表的长度。空间复杂度 O(1)。它能跑对但面试官基本不会满意因为一旦链表长了性能就崩了。不过我要说一句面试时不要一上来就憋最优解。先把暴力法说出来讲清楚它的复杂度然后说这个可以优化反而显得你思路有层次。直接甩最优解有时候面试官会怀疑你是不是背的。3.2 哈希表法用空间换时间暴力法慢在重复扫描。如果我们把链表 A 的所有节点存进一个哈希集合然后遍历链表 B第一个能在集合里找到的节点就是交点。def get_intersection_hash(headA, headB): if not headA or not headB: return None visited set() pA headA while pA: visited.add(id(pA)) pA pA.next pB headB while pB: if id(pB) in visited: return pB pB pB.next return None时间复杂度降到 O(mn)但空间复杂度变成 O(m)。这里有个细节要注意Python 里不能直接把节点对象放进 set 做成员判断因为默认的哈希是基于对象身份的虽然大多数情况能用但更稳妥的做法是用 id() 取地址。其他语言里直接用节点引用或指针即可。哈希表法在面试里是个不错的中间答案它比暴力法优雅又比最优解好想。如果你时间紧先写这个保底再往最优解推。3.3 长度差法先对齐再同步走这是我认为最符合直觉的最优解。核心逻辑是如果两个链表相交那么从交点往后是共享的。让长的链表先走长度差的步数两个指针就站在了距离交点相同的位置然后同步前进第一次相遇就是交点。def get_length(head): length 0 while head: length 1 head head.next return length def get_intersection_length_diff(headA, headB): if not headA or not headB: return None lenA get_length(headA) lenB get_length(headB) # 让 pA 指向长的链表 pA, pB headA, headB diff lenA - lenB if diff 0: pA, pB headB, headA diff -diff # 长的先走 diff 步 for _ in range(diff): pA pA.next # 同步前进 while pA and pB: if pA is pB: return pA pA pA.next pB pB.next return None时间复杂度 O(mn)空间复杂度 O(1)。这个解法逻辑清晰容易讲明白是我在面试里最推荐的写法。有个小细节值得注意先走 diff 步之后如果两个链表根本不相交那么 pA 和 pB 会同时走到 None循环结束返回 None逻辑是自洽的。不需要额外判断尾节点是否相同虽然提前判断尾节点可以快速排除不相交的情况算是一个小优化。3.4 双指针走两遍法最优雅的 O(1) 空间解法这个解法我第一次见到的时候觉得挺妙的。思路是指针 pA 从 A 走完就跳到 B 的头指针 pB 从 B 走完就跳到 A 的头。两个指针都走 abc 的总路程如果相交它们必然在交点相遇。def get_intersection_two_pointer(headA, headB): if not headA or not headB: 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为什么这个能work设 A 独有段长 aB 独有段长 b公共段长 c。pA 走的路程是 acbpB 走的路程是 bca两者相等。所以它们会在走完相同路程后同时到达交点。如果不相交那么 c0两个指针最终都会走到 None循环条件 pA is not pB 在两者都是 None 时退出返回 None。这个解法代码极短空间 O(1)时间 O(mn)。但它的可读性不如长度差法面试时如果面试官没听过这个技巧你可能需要多花点时间解释。我的建议是长度差法作为主答案双指针法作为加分项提一句。3.5 四种解法横向对比解法时间复杂度空间复杂度代码难度面试推荐度暴力双重循环O(m*n)O(1)低不推荐仅作铺垫哈希表法O(mn)O(m)低保底方案长度差法O(mn)O(1)中强烈推荐双指针走两遍O(mn)O(1)中加分项从表里能看出来长度差法和双指针法在复杂度上并列最优区别在于代码风格和解释成本。实际面试中我建议先用长度差法把逻辑讲透如果面试官追问能不能更简洁再抛出双指针法。4. 写代码时那些容易翻车的边界情况4.1 空链表和单节点链表这是最容易被忽略的。如果 headA 或 headB 是 None直接返回 None。如果两个链表都只有一个节点且是同一个节点那交点就是它如果不是同一个节点返回 None。# 空链表检查必须放在最前面 if not headA or not headB: return None我见过有人在长度差法里忘了这个检查结果 get_length 返回 0后面走 diff 步的时候直接对 None 调 next报错。这种低级错误在面试里很致命因为它暴露了你对边界不敏感。4.2 两个链表完全重合的情况如果两个链表从头节点开始就是同一个节点那交点就是头节点。长度差法里 diff 为 0两个指针同步走第一次比较就命中返回头节点。逻辑是对的但你要确保比较用的是 is 而不是 。在 Python 里 对自定义对象默认也是比较身份但如果你重写了eq方法就可能出问题。所以判定相交时统一用 is 最稳妥。其他语言里用引用比较或指针比较。4.3 不相交但长度相同的情况两个链表长度相同但不相交长度差法里 diff 为 0两个指针同步走每次比较都不相等最后同时走到 None循环退出返回 None。这个路径是通的但要注意循环条件写成 while pA and pB而不是 while pA is not pB否则两个都变成 None 时None is not None 为 False循环会退出其实也能work。但为了逻辑清晰我倾向于用 while pA and pB 加内部判断。4.4 相交点在头节点之后但长度差很大比如 A 长 100B 长 3交点在 A 的第 98 个节点。diff 是 97pA 先走 97 步然后两个指针同步走第 98 步命中。这个没问题但你要确保先走 diff 步的循环不会越界。因为 diff 一定小于等于长链表的长度所以不会走到 None 之后。注意先走 diff 步之前最好确认 diff 不超过长链表长度。虽然数学上不会超但防御性编程习惯能帮你避免很多意外。4.5 带环链表的相交判断是另一个问题如果链表可能带环那这道题就升级了。两个带环链表相交情况会复杂很多可能相交在环外可能相交在环上可能一个带环一个不带环。这种题一般会单独出不在本文讨论范围。但你要知道本文所有解法都假设链表无环。面试时如果题目没说清楚你可以主动问一句链表是否保证无环这会给面试官留下好印象。5. 面试现场怎么把这道题讲出层次感5.1 先确认题意再动手我见过不少人一听到题目就开始写代码写到一半发现理解错了。正确的做法是先花三十秒确认几个关键点相交的定义是节点相同还是值相同链表是否带环如果相交是返回交点节点还是交点的值需不需要考虑空间复杂度限制这几个问题问出来面试官会觉得你是个有工程思维的人而不是只会刷题的机器。而且这些问题确实会影响你的解法选择。5.2 从暴力法开始逐步优化不要一上来就写最优解。先说暴力法讲清楚它的复杂度然后说这个可以优化因为重复扫描了。接着引出哈希表法再说空间可以进一步优化到 O(1)最后给出长度差法或双指针法。这个递进过程展示的是你的思考路径比直接甩答案有价值得多。面试官招人不是招答案库是招能解决问题的人。你展示出从差到好的优化过程说明你具备工程上的权衡能力。5.3 画图辅助讲解链表题一定要画图。在白板上画两个 Y 字形的链表标出 a、b、c 三段长度然后指着图讲长度差法的逻辑。图一画出来面试官立刻就能跟上你的思路你讲起来也轻松。我个人的习惯是画三种情况相交、不相交、完全重合。把这三个图都画出来边界情况就覆盖得差不多了。5.4 主动分析复杂度并给出取舍建议写完代码后主动说一句这个解法时间 O(mn)空间 O(1)如果对空间没要求哈希表法代码更短但空间是 O(m)。这种主动的复杂度分析和取舍建议是区分初级和中级工程师的重要标志。面试官如果追问如果链表很长内存有限怎么办你就可以顺势说那就必须用 O(1) 空间的解法长度差法或双指针法。6. 几个我在实际练习中踩过的坑6.1 用值比较代替地址比较这是我早期最常犯的错。写代码的时候顺手写了 pA.val pB.val跑测试用例的时候因为数据凑巧没暴露问题一到真实场景就崩。后来我养成了一个习惯凡是判断两个节点是不是同一个一律用 is绝不用 。6.2 长度差法里交换指针后忘了交换 diff 的符号diff lenA - lenB if diff 0: pA, pB headB, headA diff -diff # 这行很容易忘忘了取反的话diff 是负数range(diff) 在 Python 里直接是空循环长链表没先走后面同步走就会错位。这个 bug 很隐蔽因为不报错只是结果不对。6.3 双指针法里跳转条件写错pA pA.next if pA else headB这里必须是 if pA else headB不能写成 if pA.next else headB。因为 pA 走到 None 的时候pA.next 会直接报 AttributeError。这个细节在面试手写代码时特别容易错因为紧张的时候容易顺着思路写 pA.next。6.4 忘了处理两个链表都是 None 的情况虽然题目一般不会给两个空链表但防御性检查不亏。if not headA or not headB 这一行能挡掉所有空指针相关的崩溃。6.5 在哈希表法里直接存节点对象Python 里节点对象默认是可哈希的基于 id所以直接 add 节点也能work。但如果你重写了eq和hash就可能出问题。稳妥起见存 id(node) 或者存节点本身但确保没有重写哈希方法。我一般直接存节点因为链表节点很少重写这些方法但心里要有这个意识。7. 把这道题扩展到相关变体7.1 判断两个链表是否相交但不求交点如果只判断是否相交有个更快的技巧直接比较两个链表的尾节点。如果尾节点相同就相交否则不相交。因为相交后共享尾部尾节点必然相同。def has_intersection(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这个解法时间 O(mn)空间 O(1)而且代码极简。但它只能判断是否相交不能求交点。面试时如果面试官只问是否相交你可以先给这个再补一句如果要求交点需要更完整的解法。7.2 求两个相交链表的交点带环版本如果链表带环判断相交和求交点会复杂很多。基本思路是先用快慢指针找到各自的环入口然后分情况讨论两个都无环、两个都有环、一个有环一个无环。两个都有环的情况又要分相交在环外、相交在环上、不相交三种。这块内容足够单独写一篇这里只点一下方向。7.3 合并两个有序链表时的相交处理有些场景下两个链表可能部分共享节点合并的时候要避免重复处理共享段。这种题一般会明确说明链表是否相交如果不说明你需要先判断。处理方式和本文的长度差法类似先对齐再合并。7.4 在工程代码里怎么避免链表相交带来的问题实际工程中链表相交往往意味着数据共享或内存复用。如果两个模块各自维护链表却意外共享了节点修改一个会影响另一个这是很危险的。我的经验是在链表节点里加一个 owner 标记或者用不可变节点从设计上避免意外的共享。当然这是工程层面的考虑面试题一般不会问到。8. 我个人的练习建议和收尾这道题我前前后后写过不下二十遍每次重新写都有新的体会。最开始是背代码后来是理解逻辑再后来是能给别人讲明白最后是能根据面试官的反应灵活调整解法。这个过程没有捷径就是反复写、反复讲。我的建议是先把长度差法写到闭着眼睛都能写对包括所有边界检查。然后练习双指针法理解它为什么work。最后找个人把这道题从头到尾讲一遍包括暴力法到最优解的推演过程。能讲明白才算真正掌握。另外不要只盯着这一道题。链表相交的背后是两个序列找公共部分这个更大的问题模式。理解了长度差法和双指针法的本质你再看其他类似的题比如找两个链表的第一个公共节点、判断链表是否有环、找环入口会发现它们共享很多底层思路。最后分享一个小技巧面试前把常见链表题的节点结构、边界条件、复杂度分析整理成一张卡片考前过一遍。链表题翻来覆去就那几个套路准备充分了现场就不会慌。