刷题这么多年我始终觉得链表题是面试里性价比最高的一类题目不难理解但解法空间极大从暴力到哈希再到双指针复杂度从 O(n²) 一路优化到 O(n)每一步都能拿出来聊两句。今天要聊的这道题LeetCode 里的编号是“面试题 02.07. 链表相交”我当初刷到它的时候还没意识到这个题里藏着一个足以写进段子集的解法——两个指针从各自的链表出发走完自己的路再去对方那边最后在某一个节点相遇。有人管它叫“浪漫相遇算法”名字虽然中二但背后的数学原理干净利落。这篇文章适合谁看准备面试的人、刚学完链表想刷题巩固的人、还有和我一样刷题刷到怀疑人生但不想放弃的人。我会把双指针解法掰开揉碎结合路程推导讲清楚为什么两个指针一定能相遇然后专门讲一个我实测最容易写错的地方再给出一套unordered_set哈希解法的对照实现以及三种解法的对比。全文代码以 C 为主核心思路同样适用于 Java、Python、Go。1. 面试题 02.07 链表相交这道题到底在考什么1.1 把题面说清楚找的是同一个节点不是同一个值先看题目原意给定两个单链表的头节点headA和headB找出并返回两个单链表相交的起始节点如果两个链表没有交点返回nullptr。这里的“相交”是严格意义上的节点相交指的是指针指向同一个内存地址而不是两个节点的val相等。这一点极其关键。链表节点本质上是结构体两个链表如果共享了一段节点那么从交点开始后面的所有节点地址都是完全相同的直到链尾。很多人上来就会被题目里的示例带偏因为示例里的交点val恰好是 8于是容易下意识认为“找值相等的节点”。这是典型的坑。我见过好几个同事在本地调试时用pA-val pB-val作为相遇条件结果跑简单用例能过遇到不同链表里存在相同值节点的情况就挂。记住比的是节点地址不是节点值。这道题在 LeetCode 上还有另一个编号——第 160 题“相交链表”题面几乎一样。面试题 02.07 出自《程序员面试金典》被两个题库收录其实是好事相当于白赚一次练习量。1.2 这道题真正想考察的能力作为一道“简单偏中等”的链表题它考察的点很密集链表的基本遍历能力能不能熟练地从头节点开始一步步沿着next走完整个链表。指针比较的语义理解在 C/C 里节点指针是一个地址在 Java/Python 里是一个引用判断相等是在判断“是否为同一个对象”。时间与空间复杂度的权衡暴力解很容易想但能不能写出 O(n) 时间、O(1) 空间的解法是区分刷题深度的一个分水岭。双指针思维准确地说这是一种“同步行走 路线拼接”的建模能力把链表长度差通过路线交换来抵消。在实际工程场景里“链表相交”这个问题也有对应原型。比如两个模块各自维护了一个由共享节点组成的链表公共部分在某个节点之后开始复用再比如某些内存池、对象池用链表管理空闲块时两个逻辑链表可能共享同一个物理节点区域。虽然真实代码里直接写这种结构的场景不多但“找到两条链路的公共前缀/公共节点”这种建模能力是通用的。1.3 暴力解法为什么不是答案先聊一下最容易想到的暴力做法固定headA中的每一个节点然后遍历整条headB判断是否存在相同地址的节点。时间复杂度是 O(m×n)空间是 O(1)。这里的 m 和 n 分别是两条链表的长度。暴力解在面试里能不能提能但最好不要作为最终方案。它的优势是思路直观、不容易写错适合作为“我至少有思路”的保底回答。但面试官马上会追问一句能不能优化一下这时候如果只会暴力就比较被动了。从这个暴力思路上自然延伸出一个优化方向如果我们先把链 A 的所有节点“记下来”再遍历链 B 时每走一个节点就去查“这个节点是不是见过的”那么时间能降到 O(mn)代价是额外 O(m) 的空间。这个方案就是标题里提到的unordered_set哈希解法。它的优点是实现简单、几乎不会写错缺点是空间复杂度不够好看。后面我会专门展开。而双指针解法则是在空间上做到 O(1)同时保持 O(mn) 时间属于这道题里的最优解也是最常被追问的解法。2. 双指针“浪漫相遇”解法为什么两个指针最终会在一起2.1 核心思想把两条路拼接成等长的路先设想一个场景。你和另一个人分别站在两条长度不同的跑道上你们速度相同想找到两条跑道交汇的那个点。问题是两条跑道起点不同、长度不同直接同时跑的话你们肯定会错开。解决办法说起来非常简单每个人都把两条跑道各跑一遍。你跑完自己的跑道接着去跑他的跑道他跑完自己的跑道接着去跑你的跑道。这样一来你们两个人的总路程就一样了——都是 A 跑道加 B 跑道的总长度。当两条跑道存在交汇点时你们就会在交汇点同时出现。这就是双指针解法的全部思想。代码上我们用两个指针pA和pB初始分别指向headA和headB。每一轮循环两者各走一步如果pA走到了链表末尾nullptr下一步切换到headB如果pB走到了链表末尾nullptr下一步切换到headA。关键在于切换到对方链表之后继续一路走下去直到pA和pB指向同一个节点或者同时到达nullptr。换个说法这就是“链表版的赛道交换”。人的直觉里长链表的指针会比短链表的指针晚到终点但交换路线之后两个指针的总路程都被拉成了“A全长 B全长”或者还要多一段。由于追赶的是同一段公共区域它们必然在交点会合。2.2 数学推导a b - c 的精确证明光用感觉不够面试时推荐在白板上写出下面这段推导会非常有说服力。设链表 A 的独立段长度为a链表 B 的独立段长度为b公共部分长度为c也就是从交点到链尾的节点数如果两链表不相交则c 0公共部分为空。现在两个指针同步前进。以pA为例它走过的完整路程分两个阶段阶段一从headA出发走完链表 A 的全长长度为a c此时到达尾部的nullptr。阶段二切换到headB从 B 的头节点继续走直到进入公共部分前的独立段走完长度为b此时停在交点。所以pA到达交点总共走过的步数是(a c) b a b c同理pB从headB出发走完 B 的全长b c再切换到 A 的头节点走完 A 的独立段a到达交点(b c) a a b c两个式子完全相等。也就是说从出发到相遇两个指针走过的步数一模一样。由于它们每一步都是同步前进的必然在同一时刻、同一节点相遇。如果c 0意味着没有交点。此时两个指针都走完a b步同时到达各自的nullptr循环结束返回nullptr。这也解释了为什么这道题不存在“死循环”的问题——最坏情况下两个指针会同时走到链尾的空指针。这套推导和“环形链表”里快慢指针判环的思想有本质区别。这道题的指针交换路线相当于把两个链表“首尾相接”使用的是一个非常朴素的长度补偿思想而不是速度差追及。面试现场画出这个推导基本就能证明你把双指针吃透了。2.3 C 代码实现与逐步拆解完整代码如下已经跑过 LeetCode 官方案例/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 空链表直接返回 nullptr if (headA nullptr || headB nullptr) { return nullptr; } ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { // 如果 pA 走到末尾则切到 headB否则继续走 next pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; } };逐行解释一下初始判断空链表虽然理论上如果headA为nullptr循环会直接退出并返回nullptr但显式判断可以让逻辑更清晰也避免一些不必要的三目运算。循环条件while (pA ! pB)这是核心。pA和pB相等的情况只有三种两者都指向交点两者都指向同一个尾节点两者都是nullptr。只要不相等就一直移动。三目运算符的两条赋值语句顺序无所谓但不能把判断写成pA-next nullptr那样会丢失对“当前节点就是尾部最后一个有效节点”的正确处理。正确写法里当pA等于nullptr时说明已经走过完整链表下一轮才切换头部。有相交时返回的结果就是交点无相交时pA和pB同时变成nullptr循环退出函数返回nullptr。这里有一个非常容易被忽略的细节三目运算符在pA nullptr时切换到headB而不是直接停在nullptr等另一个指针。有些读者会想如果无交点pA和pB不都已经到nullptr了吗为什么还有机会切到对方的头部呢注意循环执行的时序进入循环时两个指针都非空循环体执行一次两个指针各走一步然后回到循环条件判断。当pA和pB同时走到nullptr时在“回到循环条件判断”这个环节就会被拦住不会再执行循环体里的三目运算符。因此不存在“都已经为 nullptr 了还在互相切换”的幻觉。而在有交点的场景下两者一定在变成nullptr之前先相遇所以切换逻辑是安全的。2.4 用“路灯”类比再理解一遍如果数学推导看着晕可以换个生活化的类比。想象两条路A 路和 B 路它们在中点之后合并成一条大路。大路上有一盏路灯我们想知道路灯在哪里。两个人分别站在 A 路起点和 B 路起点同时以相同速度往前走。甲的计划是先把自己的 A 路走完再掉头走一遍 B 路。乙的计划是先把自己的 B 路走完再掉头走一遍 A 路。仔细想想甲走到大路路灯时走过的路程其实是“A 路全长 B 路独立段”乙走到同一盏路灯时走过的路程是“B 路全长 A 路独立段”。这两个值相等。于是他们同时到达路灯。双指针代码就是在模拟这两个人的行走过程遇到路的尽头不是停下来而是瞬移到另一条路的起点继续走。3. 一个关键易错点指针判空与循环条件3.1 最常见的坑把 while 条件写成 pA-next ! pB-next我见过很多刷题群里的朋友栽在这个地方。第一次写双指针时他们对“走到末尾就切到另一个链表头”这件事印象很深刻但把循环条件写成了while (pA-next ! pB-next) { // 错误示范 pA (pA-next nullptr) ? headB : pA-next; pB (pB-next nullptr) ? headA : pB-next; }这个写法的问题是如果任意一个链表只有一个节点这个节点的next就是nullptr循环一开始就可能因为空指针解引用而崩溃。如果两链表不相交它们可能永远等不到“next 相等”的时刻或者由于不断切换头部导致逻辑混乱。如果交点是尾节点pA-next和pB-next都是nullptr反而提前退出返回的不是交点。正确的核心循环条件只有一个while (pA ! pB)。判断的是“当前节点相不相同”而不是“下一个节点相不相同”。链表题里要时刻提醒自己你操作的是节点本身还是节点的next这两者差之毫厘谬以千里。3.2 另一个坑直接比较 val 而不是指针地址有相交时交点节点的val当然相等但反过来不成立。两个不相交的链表完全可以出现相同数值的节点。例如链表 A: 1 - 2 - 3 - 4 链表 B: 9 - 3 - 5 - 6链表 A 的第三个节点和链表 B 的第二个节点val都是 3但它们显然是不同的内存区域。如果代码写成while (pA-val ! pB-val) { // 错误示范 ... } return pA;这个链表会返回“值为 3 的节点 A3”而实际上 A 和 B 根本没有相交。这个错误在 C 里尤其隐蔽因为值相等时编译期不会报任何错误只有跑测试用例时才会翻车。Java 和 Python 类似比较对象相等用在 Java 里比的是引用Python 里比的是内存地址虽然语言层面天然正确但脑子里要特别明确你比较的到底是什么。3.3 边界条件空链表、单节点链表、完全相同的链表继续说坑。双指针解法对边界条件的容忍度很高但也不代表可以无脑写。空链表headA nullptr或headB nullptr时任意一条链表都没有节点不可能有交点直接返回nullptr。不加这个判断也能跑通但加了更稳。单节点链表一条链表只有一个节点另一条链表的某个节点就是它。此时两个指针第一次进入循环时一个指针指向单节点另一个指针还在走等另一个指针走到单节点时循环条件pA ! pB为假直接返回非常丝滑。两条完全相同的链表headA等于headB二者头节点相同此时循环一次都不执行直接返回headA。这当然是正确结果。把这些边界情况整理成一个自查清单刷完代码后用来自检非常方便场景预期结果双指针行为任一链表为空nullptr显式返回或循环退出两链表不相交nullptr两指针走完 mn 步后同时为nullptr交点在头节点头节点循环初始条件即满足直接返回交点在尾节点尾节点两指针同步到达尾节点两链表完全同一头节点循环不执行返回头节点3.4 为什么不需要手动计算长度差这道题还有另一种主流解法先遍历两条链表分别算出长度 m 和 n让长链表指针先走 |m-n| 步然后两个指针同步前进第一个相等处就是交点。这个解法的时间也是 O(mn)空间 O(1)。那它和双指针“浪漫相遇”解法有什么区别区别在于是否需要预处理。长度差法需要先完整遍历一遍两条链表这至少需要两趟扫描双指针法也是一趟变向的两趟扫描但因为同时在进行从常数上讲差不多。不过双指针法代码更短不需要额外变量记录长度也不需要注意“谁长谁短”的分支判断。面试时我一般推荐直接写双指针理由很简单代码不容易引入分支错误推导过程也好讲。长度差法不是不能提如果在白板上已经画出了长度差对齐的示意图面试官会认为你很稳但如果时间紧张直接上双指针是更保险的选择。4. unordered_set 哈希解法另一种思路与双指针对比4.1 哈希解法的思路与 C 实现如果不追求 O(1) 空间unordered_set解法是最容易理解的方案也是面试时可以先抛出来的“过渡答案”。思路分两步遍历链表 A把每一个节点的地址指针存入一个unordered_set遍历链表 B每走到一个节点就判断它的指针是否已经在集合里。第一个命中集合的节点就是交点如果整个 B 走完都没有命中说明没有交点。C 实现如下#include unordered_set class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* visited; ListNode *cur headA; while (cur ! nullptr) { visited.insert(cur); cur cur-next; } cur headB; while (cur ! nullptr) { if (visited.find(cur) ! visited.end()) { return cur; } cur cur-next; } return nullptr; } };这个代码里几个值得注意的点unordered_setListNode*存的是“指针”不是“值”因为这里我们要找的是节点地址是否被访问过。find(cur) ! visited.end()是 C 里判断元素是否存在的标准写法如果find返回了end()说明集合里没有该节点。第一次遍历 A 时重复节点地址不存在因为链表是一维结构不会自己指向自己形成重复。如果两条链表在中间某处相交那么交点之后的节点都会命中但我们返回的是第一个命中的也就是交点本身。在 Python 里实现更简洁因为 Python 的set本身就是哈希表class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: seen set() cur headA while cur: seen.add(cur) cur cur.next cur headB while cur: if cur in seen: return cur cur cur.next return NonePython 版里cur是对象引用放进set后判断是否存在天然就是按对象内存地址去重。4.2 时间与空间复杂度分析哈希解法的时间复杂度是 O(mn)空间复杂度是 O(m)其中 m 是链表 A 的长度。从时间复杂度看它和双指针解法没有差距都是线性级别但空间上多了 O(m) 的额外开销。对于一个节点数量很大的链表比如百万量级额外开一个哈希集合的内存开销不算小。这里有一个细节值得说为什么空间是 O(m) 而不是 O(mn)因为只存了链表 A 的所有节点。如果两条链表都很长理论上最坏情况需要哈希表容纳 A 的所有节点。如果追求更对称的空间负担也可以把较短的链表存入集合这样空间就是 O(min(m, n))。不过这道题一般不会像“找出两个数组交集”那样特别在意谁短谁长因为 O(m) 和 O(min(m,n)) 在渐进意义上都是线性面试官通常不太纠结这点。4.3 三种解法横向对比把这三种解法放在一起比较心里就有底了解法时间复杂度空间复杂度实现难度面试推荐度暴力双循环O(m×n)O(1)低不推荐unordered_set哈希O(mn)O(m)低可以用作过渡双指针路线交换O(mn)O(1)中强烈推荐我自己刷题时的习惯是先用unordered_set把题过一遍确认思路没问题然后立刻改写双指针。因为unordered_set解法代码非常短、不易出错能让你快速验证自己有没有理解“交点就是同一个节点”这件事。然后再通过双指针解法把空间复杂度优化到 O(1)顺便把路程推导在白板上画一遍。4.4 面试时怎么讲才能加分面试现场如果遇到这道题我的建议是这样的节奏先说出暴力解简单提一下“固定 A 的每个节点再遍历 B”说明你知道最朴素的做法。然后立刻说“但暴力是 O(m×n)可以用哈希表优化到 O(mn)”顺手讲一下unordered_set存节点指针的思路。面试官大概率会问“能不能把空间也优化到 O(1)”这时候引出双指针路线交换解法当场画图 写推导。最后在白板上写出双指针代码结束。这个顺序既展示了思维的递进又展示了你会多种解法、知道每个方案的代价。比直接甩出双指针更自然也更容易让面试官顺着你的思路往下问掌握对话节奏。5. 刷题实战记录与面试避坑经验5.1 我自己调试时踩过的坑说一个真实的调试经历。第一次写这道题的双指针解法时我自信满满地提交了下面这段代码while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; }结果在本地测试无交点的样例时发现输出不是nullptr而是某个奇奇怪怪的节点。排查了半天问题出在我查看结果的方式我在循环外打印了pA-val但根本没意识到此时pA已经指向了nullptr于是发生了空指针访问打印出一个随机值。这其实是一个很典型的坑只看到了“异常”的打印值误以为代码逻辑错了实际上是访问了空指针。解决方法是把打印语句改成if (pA nullptr) { cout null endl; } else { cout pA-val endl; }从那以后我养成了一个习惯凡是链表题打印节点信息前一定先判空。链表题的空指针问题太常见了一不小心就会混淆“没有交点”和“程序出错”两种情况。另一个真实的坑是环境差异。LeetCode 官方给的ListNode定义里next初始化为NULL这个NULL在 C 里其实就是nullptr但在某些老式编译环境里可能是0。用三目运算符判断pA nullptr没问题但有些朋友习惯写pA-next NULL或者pA-next 0风格混用容易带来可读性问题。尽量统一用nullptr现代 C 的最佳实践。5.2 面试官追问的套路和应对我陪朋友模拟面试时发现这道题的高频追问集中在下面这几个问题上“如果两个链表没有交点你的代码会不会死循环”答不会。没有交点时c 0两个指针各自走完m n步后同时到达nullptr循环条件pA ! pB变成false函数返回nullptr。“为什么你的两个指针第一次相遇一定是在交点而不是在交点之前的某个位置”答因为在到达交点之前pA和pB分别处于对方链表的不同独立段上走过的步数虽然相同但位置不同。只有到达交点时两者才第一次满足“处于同一节点”即满足pA pB。若两条链表没有公共部分唯一可能出现相等的情况是都为nullptr。“如果链表有环这题还能用双指针解吗”答不能直接套用需要先判断是否有环、找到环入口等属于带环链表问题是更进阶的变体。面试时如果被问到可以顺着这个点聊环形链表的判定展示知识面。“哈希解法的缺点是什么”答空间复杂度是 O(m)额外使用了一个哈希表如果面试环境对内存有要求双指针明显更优。我发现面试官其实很在意“你知不知道什么时候该停下”。无交点场景就是这道题的边界条件能清楚回答“为什么不会死循环”通常就能打消面试官的主要疑虑。5.3 这类“找公共节点”题目的通用套路链表题刷多了会发现找公共节点、找环入口、找倒数第 k 个节点很多问题本质上都围绕两个关键词对齐起点和同步行走。找链表倒数第 k 个节点快指针先走 k 步然后快慢指针同步走。判断两个链表是否相交这题本身就是所有解法都是先对齐或复用路线。找带环链表的环入口快慢指针相遇后一个指针从头开始走一个从相遇点继续走再次相遇处即入口。合并两个有序链表用哑节点 双指针逐个比较本质也是同步游走。这道题的路线交换思想本质上是一种“虚拟拼接”把 A 和 B 拼接成 AB 与 BA 两条等长路线跑步的人自然会在同一个交汇点撞见。这个思路甚至可以迁移到数组题里的“在两个数组中找公共元素”问题上只不过数组题通常没有“节点地址一致”这种天然约束需要用下标或哈希来处理。5.4 刷题时怎么安排最优时间线最后分享一下我的个人做法也算是一个章节之外的彩蛋。很多人刷题喜欢直接看题解看完 AC 就觉得完事。但算法题特别容易产生“眼高手低”的错觉看懂了 ≠ 自己能写出来。我推荐按下面这个节奏刷这类链表题先不看题解花 10 分钟尝试独立思考哪怕写暴力解也行。想出暴力解后尝试优化时间比如引入哈希表。再尝试优化空间引入双指针。AC 之后把暴力解、哈希解、双指针解三种写法都写一遍。最后在代码注释里写一句话总结这个题型的核心套路。这个流程看起来慢但对链表的理解会扎实很多。刷题不是比数量而是比“这道题给你留下了什么”。面试题 02.07 给我留下的就是“路线拼接等于长度补偿”这句话直到现在写别的题遇到类似结构我还会想起它。这道题本身不难但把它吃透链表双指针题的半壁江山就稳了。 
长河君 · 2026/10/7 3:09:45 · 阅读 1.2k 链表相交面试题详解：双指针浪漫相遇解法与数学推导
刷题这么多年我始终觉得链表题是面试里性价比最高的一类题目不难理解但解法空间极大从暴力到哈希再到双指针复杂度从 O(n²) 一路优化到 O(n)每一步都能拿出来聊两句。今天要聊的这道题LeetCode 里的编号是“面试题 02.07. 链表相交”我当初刷到它的时候还没意识到这个题里藏着一个足以写进段子集的解法——两个指针从各自的链表出发走完自己的路再去对方那边最后在某一个节点相遇。有人管它叫“浪漫相遇算法”名字虽然中二但背后的数学原理干净利落。这篇文章适合谁看准备面试的人、刚学完链表想刷题巩固的人、还有和我一样刷题刷到怀疑人生但不想放弃的人。我会把双指针解法掰开揉碎结合路程推导讲清楚为什么两个指针一定能相遇然后专门讲一个我实测最容易写错的地方再给出一套unordered_set哈希解法的对照实现以及三种解法的对比。全文代码以 C 为主核心思路同样适用于 Java、Python、Go。1. 面试题 02.07 链表相交这道题到底在考什么1.1 把题面说清楚找的是同一个节点不是同一个值先看题目原意给定两个单链表的头节点headA和headB找出并返回两个单链表相交的起始节点如果两个链表没有交点返回nullptr。这里的“相交”是严格意义上的节点相交指的是指针指向同一个内存地址而不是两个节点的val相等。这一点极其关键。链表节点本质上是结构体两个链表如果共享了一段节点那么从交点开始后面的所有节点地址都是完全相同的直到链尾。很多人上来就会被题目里的示例带偏因为示例里的交点val恰好是 8于是容易下意识认为“找值相等的节点”。这是典型的坑。我见过好几个同事在本地调试时用pA-val pB-val作为相遇条件结果跑简单用例能过遇到不同链表里存在相同值节点的情况就挂。记住比的是节点地址不是节点值。这道题在 LeetCode 上还有另一个编号——第 160 题“相交链表”题面几乎一样。面试题 02.07 出自《程序员面试金典》被两个题库收录其实是好事相当于白赚一次练习量。1.2 这道题真正想考察的能力作为一道“简单偏中等”的链表题它考察的点很密集链表的基本遍历能力能不能熟练地从头节点开始一步步沿着next走完整个链表。指针比较的语义理解在 C/C 里节点指针是一个地址在 Java/Python 里是一个引用判断相等是在判断“是否为同一个对象”。时间与空间复杂度的权衡暴力解很容易想但能不能写出 O(n) 时间、O(1) 空间的解法是区分刷题深度的一个分水岭。双指针思维准确地说这是一种“同步行走 路线拼接”的建模能力把链表长度差通过路线交换来抵消。在实际工程场景里“链表相交”这个问题也有对应原型。比如两个模块各自维护了一个由共享节点组成的链表公共部分在某个节点之后开始复用再比如某些内存池、对象池用链表管理空闲块时两个逻辑链表可能共享同一个物理节点区域。虽然真实代码里直接写这种结构的场景不多但“找到两条链路的公共前缀/公共节点”这种建模能力是通用的。1.3 暴力解法为什么不是答案先聊一下最容易想到的暴力做法固定headA中的每一个节点然后遍历整条headB判断是否存在相同地址的节点。时间复杂度是 O(m×n)空间是 O(1)。这里的 m 和 n 分别是两条链表的长度。暴力解在面试里能不能提能但最好不要作为最终方案。它的优势是思路直观、不容易写错适合作为“我至少有思路”的保底回答。但面试官马上会追问一句能不能优化一下这时候如果只会暴力就比较被动了。从这个暴力思路上自然延伸出一个优化方向如果我们先把链 A 的所有节点“记下来”再遍历链 B 时每走一个节点就去查“这个节点是不是见过的”那么时间能降到 O(mn)代价是额外 O(m) 的空间。这个方案就是标题里提到的unordered_set哈希解法。它的优点是实现简单、几乎不会写错缺点是空间复杂度不够好看。后面我会专门展开。而双指针解法则是在空间上做到 O(1)同时保持 O(mn) 时间属于这道题里的最优解也是最常被追问的解法。2. 双指针“浪漫相遇”解法为什么两个指针最终会在一起2.1 核心思想把两条路拼接成等长的路先设想一个场景。你和另一个人分别站在两条长度不同的跑道上你们速度相同想找到两条跑道交汇的那个点。问题是两条跑道起点不同、长度不同直接同时跑的话你们肯定会错开。解决办法说起来非常简单每个人都把两条跑道各跑一遍。你跑完自己的跑道接着去跑他的跑道他跑完自己的跑道接着去跑你的跑道。这样一来你们两个人的总路程就一样了——都是 A 跑道加 B 跑道的总长度。当两条跑道存在交汇点时你们就会在交汇点同时出现。这就是双指针解法的全部思想。代码上我们用两个指针pA和pB初始分别指向headA和headB。每一轮循环两者各走一步如果pA走到了链表末尾nullptr下一步切换到headB如果pB走到了链表末尾nullptr下一步切换到headA。关键在于切换到对方链表之后继续一路走下去直到pA和pB指向同一个节点或者同时到达nullptr。换个说法这就是“链表版的赛道交换”。人的直觉里长链表的指针会比短链表的指针晚到终点但交换路线之后两个指针的总路程都被拉成了“A全长 B全长”或者还要多一段。由于追赶的是同一段公共区域它们必然在交点会合。2.2 数学推导a b - c 的精确证明光用感觉不够面试时推荐在白板上写出下面这段推导会非常有说服力。设链表 A 的独立段长度为a链表 B 的独立段长度为b公共部分长度为c也就是从交点到链尾的节点数如果两链表不相交则c 0公共部分为空。现在两个指针同步前进。以pA为例它走过的完整路程分两个阶段阶段一从headA出发走完链表 A 的全长长度为a c此时到达尾部的nullptr。阶段二切换到headB从 B 的头节点继续走直到进入公共部分前的独立段走完长度为b此时停在交点。所以pA到达交点总共走过的步数是(a c) b a b c同理pB从headB出发走完 B 的全长b c再切换到 A 的头节点走完 A 的独立段a到达交点(b c) a a b c两个式子完全相等。也就是说从出发到相遇两个指针走过的步数一模一样。由于它们每一步都是同步前进的必然在同一时刻、同一节点相遇。如果c 0意味着没有交点。此时两个指针都走完a b步同时到达各自的nullptr循环结束返回nullptr。这也解释了为什么这道题不存在“死循环”的问题——最坏情况下两个指针会同时走到链尾的空指针。这套推导和“环形链表”里快慢指针判环的思想有本质区别。这道题的指针交换路线相当于把两个链表“首尾相接”使用的是一个非常朴素的长度补偿思想而不是速度差追及。面试现场画出这个推导基本就能证明你把双指针吃透了。2.3 C 代码实现与逐步拆解完整代码如下已经跑过 LeetCode 官方案例/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 空链表直接返回 nullptr if (headA nullptr || headB nullptr) { return nullptr; } ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { // 如果 pA 走到末尾则切到 headB否则继续走 next pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; } };逐行解释一下初始判断空链表虽然理论上如果headA为nullptr循环会直接退出并返回nullptr但显式判断可以让逻辑更清晰也避免一些不必要的三目运算。循环条件while (pA ! pB)这是核心。pA和pB相等的情况只有三种两者都指向交点两者都指向同一个尾节点两者都是nullptr。只要不相等就一直移动。三目运算符的两条赋值语句顺序无所谓但不能把判断写成pA-next nullptr那样会丢失对“当前节点就是尾部最后一个有效节点”的正确处理。正确写法里当pA等于nullptr时说明已经走过完整链表下一轮才切换头部。有相交时返回的结果就是交点无相交时pA和pB同时变成nullptr循环退出函数返回nullptr。这里有一个非常容易被忽略的细节三目运算符在pA nullptr时切换到headB而不是直接停在nullptr等另一个指针。有些读者会想如果无交点pA和pB不都已经到nullptr了吗为什么还有机会切到对方的头部呢注意循环执行的时序进入循环时两个指针都非空循环体执行一次两个指针各走一步然后回到循环条件判断。当pA和pB同时走到nullptr时在“回到循环条件判断”这个环节就会被拦住不会再执行循环体里的三目运算符。因此不存在“都已经为 nullptr 了还在互相切换”的幻觉。而在有交点的场景下两者一定在变成nullptr之前先相遇所以切换逻辑是安全的。2.4 用“路灯”类比再理解一遍如果数学推导看着晕可以换个生活化的类比。想象两条路A 路和 B 路它们在中点之后合并成一条大路。大路上有一盏路灯我们想知道路灯在哪里。两个人分别站在 A 路起点和 B 路起点同时以相同速度往前走。甲的计划是先把自己的 A 路走完再掉头走一遍 B 路。乙的计划是先把自己的 B 路走完再掉头走一遍 A 路。仔细想想甲走到大路路灯时走过的路程其实是“A 路全长 B 路独立段”乙走到同一盏路灯时走过的路程是“B 路全长 A 路独立段”。这两个值相等。于是他们同时到达路灯。双指针代码就是在模拟这两个人的行走过程遇到路的尽头不是停下来而是瞬移到另一条路的起点继续走。3. 一个关键易错点指针判空与循环条件3.1 最常见的坑把 while 条件写成 pA-next ! pB-next我见过很多刷题群里的朋友栽在这个地方。第一次写双指针时他们对“走到末尾就切到另一个链表头”这件事印象很深刻但把循环条件写成了while (pA-next ! pB-next) { // 错误示范 pA (pA-next nullptr) ? headB : pA-next; pB (pB-next nullptr) ? headA : pB-next; }这个写法的问题是如果任意一个链表只有一个节点这个节点的next就是nullptr循环一开始就可能因为空指针解引用而崩溃。如果两链表不相交它们可能永远等不到“next 相等”的时刻或者由于不断切换头部导致逻辑混乱。如果交点是尾节点pA-next和pB-next都是nullptr反而提前退出返回的不是交点。正确的核心循环条件只有一个while (pA ! pB)。判断的是“当前节点相不相同”而不是“下一个节点相不相同”。链表题里要时刻提醒自己你操作的是节点本身还是节点的next这两者差之毫厘谬以千里。3.2 另一个坑直接比较 val 而不是指针地址有相交时交点节点的val当然相等但反过来不成立。两个不相交的链表完全可以出现相同数值的节点。例如链表 A: 1 - 2 - 3 - 4 链表 B: 9 - 3 - 5 - 6链表 A 的第三个节点和链表 B 的第二个节点val都是 3但它们显然是不同的内存区域。如果代码写成while (pA-val ! pB-val) { // 错误示范 ... } return pA;这个链表会返回“值为 3 的节点 A3”而实际上 A 和 B 根本没有相交。这个错误在 C 里尤其隐蔽因为值相等时编译期不会报任何错误只有跑测试用例时才会翻车。Java 和 Python 类似比较对象相等用在 Java 里比的是引用Python 里比的是内存地址虽然语言层面天然正确但脑子里要特别明确你比较的到底是什么。3.3 边界条件空链表、单节点链表、完全相同的链表继续说坑。双指针解法对边界条件的容忍度很高但也不代表可以无脑写。空链表headA nullptr或headB nullptr时任意一条链表都没有节点不可能有交点直接返回nullptr。不加这个判断也能跑通但加了更稳。单节点链表一条链表只有一个节点另一条链表的某个节点就是它。此时两个指针第一次进入循环时一个指针指向单节点另一个指针还在走等另一个指针走到单节点时循环条件pA ! pB为假直接返回非常丝滑。两条完全相同的链表headA等于headB二者头节点相同此时循环一次都不执行直接返回headA。这当然是正确结果。把这些边界情况整理成一个自查清单刷完代码后用来自检非常方便场景预期结果双指针行为任一链表为空nullptr显式返回或循环退出两链表不相交nullptr两指针走完 mn 步后同时为nullptr交点在头节点头节点循环初始条件即满足直接返回交点在尾节点尾节点两指针同步到达尾节点两链表完全同一头节点循环不执行返回头节点3.4 为什么不需要手动计算长度差这道题还有另一种主流解法先遍历两条链表分别算出长度 m 和 n让长链表指针先走 |m-n| 步然后两个指针同步前进第一个相等处就是交点。这个解法的时间也是 O(mn)空间 O(1)。那它和双指针“浪漫相遇”解法有什么区别区别在于是否需要预处理。长度差法需要先完整遍历一遍两条链表这至少需要两趟扫描双指针法也是一趟变向的两趟扫描但因为同时在进行从常数上讲差不多。不过双指针法代码更短不需要额外变量记录长度也不需要注意“谁长谁短”的分支判断。面试时我一般推荐直接写双指针理由很简单代码不容易引入分支错误推导过程也好讲。长度差法不是不能提如果在白板上已经画出了长度差对齐的示意图面试官会认为你很稳但如果时间紧张直接上双指针是更保险的选择。4. unordered_set 哈希解法另一种思路与双指针对比4.1 哈希解法的思路与 C 实现如果不追求 O(1) 空间unordered_set解法是最容易理解的方案也是面试时可以先抛出来的“过渡答案”。思路分两步遍历链表 A把每一个节点的地址指针存入一个unordered_set遍历链表 B每走到一个节点就判断它的指针是否已经在集合里。第一个命中集合的节点就是交点如果整个 B 走完都没有命中说明没有交点。C 实现如下#include unordered_set class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* visited; ListNode *cur headA; while (cur ! nullptr) { visited.insert(cur); cur cur-next; } cur headB; while (cur ! nullptr) { if (visited.find(cur) ! visited.end()) { return cur; } cur cur-next; } return nullptr; } };这个代码里几个值得注意的点unordered_setListNode*存的是“指针”不是“值”因为这里我们要找的是节点地址是否被访问过。find(cur) ! visited.end()是 C 里判断元素是否存在的标准写法如果find返回了end()说明集合里没有该节点。第一次遍历 A 时重复节点地址不存在因为链表是一维结构不会自己指向自己形成重复。如果两条链表在中间某处相交那么交点之后的节点都会命中但我们返回的是第一个命中的也就是交点本身。在 Python 里实现更简洁因为 Python 的set本身就是哈希表class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: seen set() cur headA while cur: seen.add(cur) cur cur.next cur headB while cur: if cur in seen: return cur cur cur.next return NonePython 版里cur是对象引用放进set后判断是否存在天然就是按对象内存地址去重。4.2 时间与空间复杂度分析哈希解法的时间复杂度是 O(mn)空间复杂度是 O(m)其中 m 是链表 A 的长度。从时间复杂度看它和双指针解法没有差距都是线性级别但空间上多了 O(m) 的额外开销。对于一个节点数量很大的链表比如百万量级额外开一个哈希集合的内存开销不算小。这里有一个细节值得说为什么空间是 O(m) 而不是 O(mn)因为只存了链表 A 的所有节点。如果两条链表都很长理论上最坏情况需要哈希表容纳 A 的所有节点。如果追求更对称的空间负担也可以把较短的链表存入集合这样空间就是 O(min(m, n))。不过这道题一般不会像“找出两个数组交集”那样特别在意谁短谁长因为 O(m) 和 O(min(m,n)) 在渐进意义上都是线性面试官通常不太纠结这点。4.3 三种解法横向对比把这三种解法放在一起比较心里就有底了解法时间复杂度空间复杂度实现难度面试推荐度暴力双循环O(m×n)O(1)低不推荐unordered_set哈希O(mn)O(m)低可以用作过渡双指针路线交换O(mn)O(1)中强烈推荐我自己刷题时的习惯是先用unordered_set把题过一遍确认思路没问题然后立刻改写双指针。因为unordered_set解法代码非常短、不易出错能让你快速验证自己有没有理解“交点就是同一个节点”这件事。然后再通过双指针解法把空间复杂度优化到 O(1)顺便把路程推导在白板上画一遍。4.4 面试时怎么讲才能加分面试现场如果遇到这道题我的建议是这样的节奏先说出暴力解简单提一下“固定 A 的每个节点再遍历 B”说明你知道最朴素的做法。然后立刻说“但暴力是 O(m×n)可以用哈希表优化到 O(mn)”顺手讲一下unordered_set存节点指针的思路。面试官大概率会问“能不能把空间也优化到 O(1)”这时候引出双指针路线交换解法当场画图 写推导。最后在白板上写出双指针代码结束。这个顺序既展示了思维的递进又展示了你会多种解法、知道每个方案的代价。比直接甩出双指针更自然也更容易让面试官顺着你的思路往下问掌握对话节奏。5. 刷题实战记录与面试避坑经验5.1 我自己调试时踩过的坑说一个真实的调试经历。第一次写这道题的双指针解法时我自信满满地提交了下面这段代码while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; }结果在本地测试无交点的样例时发现输出不是nullptr而是某个奇奇怪怪的节点。排查了半天问题出在我查看结果的方式我在循环外打印了pA-val但根本没意识到此时pA已经指向了nullptr于是发生了空指针访问打印出一个随机值。这其实是一个很典型的坑只看到了“异常”的打印值误以为代码逻辑错了实际上是访问了空指针。解决方法是把打印语句改成if (pA nullptr) { cout null endl; } else { cout pA-val endl; }从那以后我养成了一个习惯凡是链表题打印节点信息前一定先判空。链表题的空指针问题太常见了一不小心就会混淆“没有交点”和“程序出错”两种情况。另一个真实的坑是环境差异。LeetCode 官方给的ListNode定义里next初始化为NULL这个NULL在 C 里其实就是nullptr但在某些老式编译环境里可能是0。用三目运算符判断pA nullptr没问题但有些朋友习惯写pA-next NULL或者pA-next 0风格混用容易带来可读性问题。尽量统一用nullptr现代 C 的最佳实践。5.2 面试官追问的套路和应对我陪朋友模拟面试时发现这道题的高频追问集中在下面这几个问题上“如果两个链表没有交点你的代码会不会死循环”答不会。没有交点时c 0两个指针各自走完m n步后同时到达nullptr循环条件pA ! pB变成false函数返回nullptr。“为什么你的两个指针第一次相遇一定是在交点而不是在交点之前的某个位置”答因为在到达交点之前pA和pB分别处于对方链表的不同独立段上走过的步数虽然相同但位置不同。只有到达交点时两者才第一次满足“处于同一节点”即满足pA pB。若两条链表没有公共部分唯一可能出现相等的情况是都为nullptr。“如果链表有环这题还能用双指针解吗”答不能直接套用需要先判断是否有环、找到环入口等属于带环链表问题是更进阶的变体。面试时如果被问到可以顺着这个点聊环形链表的判定展示知识面。“哈希解法的缺点是什么”答空间复杂度是 O(m)额外使用了一个哈希表如果面试环境对内存有要求双指针明显更优。我发现面试官其实很在意“你知不知道什么时候该停下”。无交点场景就是这道题的边界条件能清楚回答“为什么不会死循环”通常就能打消面试官的主要疑虑。5.3 这类“找公共节点”题目的通用套路链表题刷多了会发现找公共节点、找环入口、找倒数第 k 个节点很多问题本质上都围绕两个关键词对齐起点和同步行走。找链表倒数第 k 个节点快指针先走 k 步然后快慢指针同步走。判断两个链表是否相交这题本身就是所有解法都是先对齐或复用路线。找带环链表的环入口快慢指针相遇后一个指针从头开始走一个从相遇点继续走再次相遇处即入口。合并两个有序链表用哑节点 双指针逐个比较本质也是同步游走。这道题的路线交换思想本质上是一种“虚拟拼接”把 A 和 B 拼接成 AB 与 BA 两条等长路线跑步的人自然会在同一个交汇点撞见。这个思路甚至可以迁移到数组题里的“在两个数组中找公共元素”问题上只不过数组题通常没有“节点地址一致”这种天然约束需要用下标或哈希来处理。5.4 刷题时怎么安排最优时间线最后分享一下我的个人做法也算是一个章节之外的彩蛋。很多人刷题喜欢直接看题解看完 AC 就觉得完事。但算法题特别容易产生“眼高手低”的错觉看懂了 ≠ 自己能写出来。我推荐按下面这个节奏刷这类链表题先不看题解花 10 分钟尝试独立思考哪怕写暴力解也行。想出暴力解后尝试优化时间比如引入哈希表。再尝试优化空间引入双指针。AC 之后把暴力解、哈希解、双指针解三种写法都写一遍。最后在代码注释里写一句话总结这个题型的核心套路。这个流程看起来慢但对链表的理解会扎实很多。刷题不是比数量而是比“这道题给你留下了什么”。面试题 02.07 给我留下的就是“路线拼接等于长度补偿”这句话直到现在写别的题遇到类似结构我还会想起它。这道题本身不难但把它吃透链表双指针题的半壁江山就稳了。