空间解法精讲)
链表题在面试里属于看起来简单翻车率却极高的一类。LeetCode面试题2.7的链表相交问题恰好就是这样一道典型的陷阱题很多人在反转链表和合并链表上练得很熟但一遇到两个链表的相交判断就开始用双重循环暴力解然后被面试官追问能不能优化到O(n)时哑口无言。这篇blog就围绕这道题的C双指针解法从题目本质、数学原理、代码实现到边界场景把整个思路链条完整捋一遍顺便分享一些我在实际刷题和模拟面试中总结出的细节经验。1. 面试题2.7到底在考什么从暴力解法到双指针的动机1.1 题目描述与第一反应题目本身并不复杂输入两个单向链表判断它们是否相交如果相交则返回相交的起始节点否则返回空指针。所谓的相交不是两个节点的val相等而是两个链表从某个节点开始共享同一批节点对象。一个经典例子是链表A4 - 1 - 8 - 4 - 5链表B5 - 0 - 1 - 8 - 4 - 5这里链表A和链表B在值为8的节点处相交之后的所有节点都是同一个对象。注意1 - 8这个片段可能让不少人误判以为只要找到第一个值相等的节点就行但链表相交是对象层面的共享不是值层面的相同。面试官最喜欢在这上面挖坑先让你手写然后故意举个例子说链表A和链表B里有值相同的节点但不相交让你解释算法为什么还能正确工作。我的第一反应和大多数人一样先把其中一个链表的所有节点指针存进哈希集合然后遍历另一个链表第一个在集合中存在的指针就是相交点。代码很简单class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* visited; ListNode* p headA; while (p ! nullptr) { visited.insert(p); p p-next; } p headB; while (p ! nullptr) { if (visited.count(p)) return p; p p-next; } return nullptr; } };这个解法能过测试时间复杂度O(n m)但空间复杂度O(n)。对于LeetCode来说这个答案可以接受但放在面试里面试官下一句话基本就是能不能用O(1)的空间这时候如果你只会哈希表就会比较被动。1.2 为什么这道题值得单独拎出来讲链表相交问题的价值在于它不像反转链表那样只有操作指针这一个考点。它本质上考察的是你能否把两个不同长度的线性结构通过某种补全手段变成等长的比较。这种抽象能力放在很多场景都通用——比如合并两个有序数组、字符串匹配中的对齐问题让两边长度一致是个很常见的解题思路。另一个容易忽略的点是这道题是LeetCode原题160Intersection of Two Linked Lists在《程序员面试金典》里是面试题2.7在剑指Offer里是第52题只是一个表达方式的差别。你刷题时会发现同一个核心考点在多个题库中反复出现如果只记住代码没理解原理换个马甲就又认不出来了。所以我建议把这题当作双指针思想训练题来对待而不仅仅是一个孤立题的答案。2. 双指针法的核心直觉为什么错身而过的指针一定能相遇2.1 最朴素的正向思路先消除长度差从暴力法跳到双指针法其实是有一个中间过渡的。我们先从消除长度差入手这也是最容易向面试官讲清楚的思路先分别遍历两个链表得到长度lenA和lenB让较长的链表指针先走|lenA - lenB|步然后两个指针同步前进第一个相遇的节点就是答案。class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA 0, lenB 0; ListNode* pA headA; ListNode* pB headB; while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } pA headA; pB headB; int diff lenA - lenB; if (diff 0) { while (diff--) pA pA-next; } else { diff -diff; while (diff--) pB pB-next; } while (pA pB pA ! pB) { pA pA-next; pB pB-next; } return pA; } };这个解法的时间复杂度是O(n m)空间O(1)。面试中如果先给出这个版本已经算及格。但它有个不够优雅的地方需要两次完整遍历才能得到长度信息而且要先处理长度差。2.2 双指针的真正巧妙之处复用路径补足长度差双指针法跳出了数长度的思维定式它不去显式计算长度差而是让两个指针都按照同样一条规则行动每次走一步走到链表末尾后就跳到另一个链表的头节点继续走。当两个链表相交时我们假设链表A在相交前的独占部分长度为a链表B在相交前的独占部分长度为b公共部分长度为c。指针pA从headA出发走完自己的链表a c然后跳到headB继续走b步此时pA总共走了a c b指针pB从headB出发走完自己的链表b c然后跳到headA继续走a步此时pB总共走了b c a。两个式子完全相等而且在走完这些步数时两个指针恰好都落在相交节点上。这个恰好落在相交节点才是关键。虽然两个指针起始位置不同走过的链表组成不同但总步长被设计成了同一个值于是在最后一次同步移动时它们会在相同步数内同时到达相交点。就像两个人从不同地点出发其中一个人先进了一个环形通道另一个人走了一段直线后再进入同一个环形通道只要保证总路程一致他们终会在通道里的某个点碰头。2.3 用具体例子走一遍全过程我们拿前面的例子来手动走一遍链表A4 - 1 - 8 - 4 - 5 链表B5 - 0 - 1 - 8 - 4 - 5这里的相交节点是值为8的节点。假设节点对象的地址分别是n4, n1, n8, n4p, n5p和n5, n0, n1p, n8, n4p, n5p。pA和pB同时出发第1步pA到1pB到0第2步pA到8pB到1p第3步pA到4ppB到8第4步pA到5ppB到4p第5步pA到nullptrpB到5p第6步pA跳到headB即5pB跳到headA即4第7步pA到0pB到1第8步pA到1ppB到8第9步pA到8pB到4p第10步pA到4ppB到5p第11步pA到5ppB到nullptrpB跳到headA第12步pA跳到headA即4pB到1第13步pA到1pB到8第14步pA到8pB到4p第15步pA到4ppB到5p第16步pA到5ppB到nullptrpB跳到headA第17步pA跳到headA即4pB到1 ……仔细数会发现这个例子里的A和B其实长度不同走法比较复杂。换个简单一点的例子更容易说明白设A的独占部分a2节点A1-A2B的独占部分b3节点B1-B2-B3公共部分c2节点C1-C2。pA走A1,A2,C1,C2然后到nullptr后跳到B1走B1,B2,B3再走C1此时到达C1。pB走B1,B2,B3,C1,C2nullptr后跳到A1走A1,A2再走C1也是到达C1。它们走的总步数都是7且都停在C1。当链表不相交时两个指针都会走完两个链表的所有节点同时到达nullptr此时pA和pB都为空循环结束返回空指针不会死循环。3. C实现细节打磨代码怎么写才不容易在面试现场翻车3.1 最精简的C解法样式双指针法的C实现可以非常短短到面试时两三行就把核心逻辑写完。这里给出我最常用的一版class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; } };这段代码的核心就是循环里的三目运算符如果当前指针不为空就向后移动一步为空就跳到另一个链表的头部。写法极度简洁但有一个隐患它没有显式处理headA和headB同时为nullptr的情况不过由于初始时pA pB nullptrwhile循环根本不会进入直接返回nullptr所以行为是正确的。3.2 逐行拆解为什么这样写更稳很多人的第一版代码不是上面这样写的而是用if判断while (pA ! pB) { if (pA nullptr) { pA headB; } else { pA pA-next; } if (pB nullptr) { pB headA; } else { pB pB-next; } } return pA;这个版本逻辑更清晰适合作为面试时的口头讲解版。三目运算符版本更简洁但我建议面试时优先用if版本因为它能展示你对边界条件的把控而不是炫技。两种版本的执行结果完全一致。我还有一个偏好指针变量名用pA和pB而不是a和b或pa和pb。在面试中手写代码时pA - pB的对称性一眼就能看出来你自己追溯逻辑的时候也更省力。别小看命名面试现场本来就很紧张命名越对称你讲起来越顺畅。3.3 关键细节为什么可以不判空直接返回这段代码最容易被问到的点是如果两个链表不相交pA和pB会不会一直互不相同导致死循环答案是不会。原因是两个指针走过的总步数一致。假设链表A长度为lenA链表B长度为lenB那么pA在遍历完lenA个节点后又遍历完lenB个节点总共经过lenA lenB个节点后变为nullptrpB也经过lenB lenA个节点后变为nullptr。两者成为nullptr的时机完全相同所以在pA ! pB这个条件中最终会出现pA和pB都为nullptr的情况此时循环条件不满足退出循环。还有一个细节容易被忽略当两个链表不相交且其中一个为空时while循环会不会误判假设headA为空而headB不为空初始pA nullptrpB headB条件pA ! pB成立进入循环。pA被赋值为headBpB向后走一步。这个行为乍一看有点奇怪但最终两个指针都会走完整条B链表再加上一条空链表然后在某一步同时变成nullptr退出循环返回nullptr结果正确。不过这种写法确实绕我建议在代码里加一个前置判空既清晰又不影响性能if (headA nullptr || headB nullptr) return nullptr;虽然不加也能得到正确答案但加上之后逻辑从第一行就非常顺面试官扫一眼就知道你考虑过空链表的边界。4. 边界场景专项排查空链表、不相交与其他刁钻输入4.1 空链表与单节点链表第一个边界场景是空链表。如果headA或headB为nullptr那么两个链表不可能相交应直接返回nullptr。这一点在双指针版代码中其实天然成立但如果面试官让你先讲思路你最好把空链表直接排除放在第一步讲而不是等代码写出来再说。第二个边界场景是单节点链表。两个单节点链表如果相交说明它们指向同一个节点对象也就是headA headB直接返回这个节点即可。如果它们各自指向不同节点则不相交返回nullptr。这段逻辑同样被双指针法自动覆盖但如果你先写计算长度差的版本就需要额外注意长度差为0时两个指针初始位置相同直接进入while循环判断不会出错。4.2 两个链表完全相同的情况当一个链表完全包含另一个链表比如链表A就是链表B的前半段那么两个链表在headA处就相交。这种情况下长度差版本的算法会让较短的链表指针先不动、较长的链表指针先走diff步然后两个指针从头开始同步走第一步就会相遇程序直接返回headA。双指针版本的算法则不关心谁长谁短它无条件地让两个指针走完两条链表最终自然在headA处相遇。我遇到过一种误判场景链表A和链表B相交后公共部分不是从相交点开始的所有节点而是中间某段共享后面又分开了。严格来说这不符合单向链表相交后必定完全重合的定义。单向链表的节点只有一个next指针两个链表一旦在某个节点相交之后的所有节点必然都是同一个对象序列无法再分离。所以看到相交后又分开的描述基本可以断定题目表述有误或者你对相交的理解有偏差。4.3 不相交链表与性能边界不相交的链表是双指针法最有意思的边界情况。之前提到过它们会在同时变为nullptr时退出循环返回nullptr。但这个过程中每个指针实际上都遍历了lenA lenB个节点。如果lenA 100000lenB 100000每个指针要走200000步整体时间复杂度依然是O(n m)没有额外空间消耗完全可以接受。我曾在一次自测中故意用两个长度悬殊且不相交的链表测试比如lenA 1lenB 100000。此时pA先走完A马上跳到B然后基本就是陪着pB把B走到头直到两者都变nullptr。整个过程没有报错也没有死循环性能在毫秒级。这说明只要理解总步数相同这一保证各种长度组合都在控制范围内。4.4 一个刁钻的输入相交节点在链表的最后一个节点有些测试用例会把相交节点设置为链表的最后一个元素。比如链表A [1,2,3]链表B [4,5,3]其中值为3的节点是同一个对象。这种情况下使用双指针法时两个指针会在最后一步同时走到这个节点然后返回。如果用长度差版本也是差多少走多少最后同步走到最后一个节点。这个边界并不特殊只是想提醒你不要假设两个链表一定在中间某个位置相交尾节点相交的情况是合法的。5. 从链表相交到环检测一道题的延伸思考5.1 双指针思想的统一视角链表相交的解法之所以经典不仅仅是因为它能用O(1)空间解决一个看似需要哈希表的问题更重要的是它展示了一种可迁移的思维通过补全长度的额外路径来把两个不同长度的遍历变成同步遍历。同样的思想换一个场景就变成了快慢指针判环。在环形链表中快指针每次走两步慢指针每次走一步它们总会相遇因为快指针相对慢指针以每次一步的速度逼近最终一定会追上。链表相交的双指针法和快慢指针法本质上是同一套同步移动数学相等性的思路只是应用的约束不同。如果你在面试中已经讲完链表相交的双指针解法面试官追问那怎么判断一个链表有没有环这时候你其实有了一个很好的衔接话术就和刚才的双指针类似不过这次是一个思路的变体让两个指针以不同速度走同一个链表。这种跨题目的联想能力往往比背十道题的代码更能打动面试官。5.2 实际开发中哪里会遇到链表相交检测很多人以为链表相交只是面试题现实工程中根本用不到。其实不然。我所知道的一个真实案例是某复杂系统的调试模块中使用了类似链表的对象引用链来记录资源依赖关系。当两个不同的资源引用链出现重叠时就说明存在共享子模块系统需要定位这个共享点来进行统一回收或缓存失效。这时候判断两个链表是否相交以及找到相交起始点就非常关键。还有一个场景是版本管理系统的对象图分析两个不同的变更序列可能共享同一个基础版本节点找出共享节点能帮助计算最小合并成本。当然工程中的链表往往不是教科书上那种单链表可能带有额外信息或双向指针但核心的双指针走两遍思路依然适用。这也是刷算法题的价值所在你未必会在业务代码里直接调用getIntersectionNode但你会经常遇到让两个不同序列对齐到同一个参考点这类问题。5.3 面试现场的讲解节奏建议根据我模拟面试的经验这道题最稳的讲解流程是先问清楚相交是指向同一个节点对象不是值相等。先说暴力法双重循环逐个比较O(n*m)时间O(1)空间太慢。再说哈希法O(nm)时间O(n)空间可以但不是最优。然后引出双指针先讲长度差消除版本再讲走两遍自动对齐版本说明后者代码更短且不需要预先遍历求长度。手动模拟一个小例子证明两个指针会相遇。说明边界空链表、不相交链表、都为空的情况。这套流程下来面试官基本能看到你的完整思考过程而不是背了一个答案。我在实际模拟面试中试过这个节奏效果很好最后一个问题基本都会变成如果链表有环会怎么样这种延伸讨论。关于这道题我个人刷了不下五遍每一遍都能找到新的理解角度。从最初背下代码到后来能推导出相遇的数学条件再到能把双指针思想迁移到其他问题中间经历的其实不是多刷题而是多问自己为什么。如果你也在准备技术面试我建议不要满足于把这段代码默写出来而是自己造几个链表例子把手动走一遍的过程写在纸上直到你能闭着眼睛说出pA走了lenAlenB步pB也走了lenBlenA步所以它们同时到nullptr或同时到交点这句话。做到这个程度面试官哪怕临时换个问法也难不倒你。
链表题在面试里属于看起来简单翻车率却极高的一类。LeetCode面试题2.7的链表相交问题恰好就是这样一道典型的陷阱题很多人在反转链表和合并链表上练得很熟但一遇到两个链表的相交判断就开始用双重循环暴力解然后被面试官追问能不能优化到O(n)时哑口无言。这篇blog就围绕这道题的C双指针解法从题目本质、数学原理、代码实现到边界场景把整个思路链条完整捋一遍顺便分享一些我在实际刷题和模拟面试中总结出的细节经验。1. 面试题2.7到底在考什么从暴力解法到双指针的动机1.1 题目描述与第一反应题目本身并不复杂输入两个单向链表判断它们是否相交如果相交则返回相交的起始节点否则返回空指针。所谓的相交不是两个节点的val相等而是两个链表从某个节点开始共享同一批节点对象。一个经典例子是链表A4 - 1 - 8 - 4 - 5链表B5 - 0 - 1 - 8 - 4 - 5这里链表A和链表B在值为8的节点处相交之后的所有节点都是同一个对象。注意1 - 8这个片段可能让不少人误判以为只要找到第一个值相等的节点就行但链表相交是对象层面的共享不是值层面的相同。面试官最喜欢在这上面挖坑先让你手写然后故意举个例子说链表A和链表B里有值相同的节点但不相交让你解释算法为什么还能正确工作。我的第一反应和大多数人一样先把其中一个链表的所有节点指针存进哈希集合然后遍历另一个链表第一个在集合中存在的指针就是相交点。代码很简单class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* visited; ListNode* p headA; while (p ! nullptr) { visited.insert(p); p p-next; } p headB; while (p ! nullptr) { if (visited.count(p)) return p; p p-next; } return nullptr; } };这个解法能过测试时间复杂度O(n m)但空间复杂度O(n)。对于LeetCode来说这个答案可以接受但放在面试里面试官下一句话基本就是能不能用O(1)的空间这时候如果你只会哈希表就会比较被动。1.2 为什么这道题值得单独拎出来讲链表相交问题的价值在于它不像反转链表那样只有操作指针这一个考点。它本质上考察的是你能否把两个不同长度的线性结构通过某种补全手段变成等长的比较。这种抽象能力放在很多场景都通用——比如合并两个有序数组、字符串匹配中的对齐问题让两边长度一致是个很常见的解题思路。另一个容易忽略的点是这道题是LeetCode原题160Intersection of Two Linked Lists在《程序员面试金典》里是面试题2.7在剑指Offer里是第52题只是一个表达方式的差别。你刷题时会发现同一个核心考点在多个题库中反复出现如果只记住代码没理解原理换个马甲就又认不出来了。所以我建议把这题当作双指针思想训练题来对待而不仅仅是一个孤立题的答案。2. 双指针法的核心直觉为什么错身而过的指针一定能相遇2.1 最朴素的正向思路先消除长度差从暴力法跳到双指针法其实是有一个中间过渡的。我们先从消除长度差入手这也是最容易向面试官讲清楚的思路先分别遍历两个链表得到长度lenA和lenB让较长的链表指针先走|lenA - lenB|步然后两个指针同步前进第一个相遇的节点就是答案。class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA 0, lenB 0; ListNode* pA headA; ListNode* pB headB; while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } pA headA; pB headB; int diff lenA - lenB; if (diff 0) { while (diff--) pA pA-next; } else { diff -diff; while (diff--) pB pB-next; } while (pA pB pA ! pB) { pA pA-next; pB pB-next; } return pA; } };这个解法的时间复杂度是O(n m)空间O(1)。面试中如果先给出这个版本已经算及格。但它有个不够优雅的地方需要两次完整遍历才能得到长度信息而且要先处理长度差。2.2 双指针的真正巧妙之处复用路径补足长度差双指针法跳出了数长度的思维定式它不去显式计算长度差而是让两个指针都按照同样一条规则行动每次走一步走到链表末尾后就跳到另一个链表的头节点继续走。当两个链表相交时我们假设链表A在相交前的独占部分长度为a链表B在相交前的独占部分长度为b公共部分长度为c。指针pA从headA出发走完自己的链表a c然后跳到headB继续走b步此时pA总共走了a c b指针pB从headB出发走完自己的链表b c然后跳到headA继续走a步此时pB总共走了b c a。两个式子完全相等而且在走完这些步数时两个指针恰好都落在相交节点上。这个恰好落在相交节点才是关键。虽然两个指针起始位置不同走过的链表组成不同但总步长被设计成了同一个值于是在最后一次同步移动时它们会在相同步数内同时到达相交点。就像两个人从不同地点出发其中一个人先进了一个环形通道另一个人走了一段直线后再进入同一个环形通道只要保证总路程一致他们终会在通道里的某个点碰头。2.3 用具体例子走一遍全过程我们拿前面的例子来手动走一遍链表A4 - 1 - 8 - 4 - 5 链表B5 - 0 - 1 - 8 - 4 - 5这里的相交节点是值为8的节点。假设节点对象的地址分别是n4, n1, n8, n4p, n5p和n5, n0, n1p, n8, n4p, n5p。pA和pB同时出发第1步pA到1pB到0第2步pA到8pB到1p第3步pA到4ppB到8第4步pA到5ppB到4p第5步pA到nullptrpB到5p第6步pA跳到headB即5pB跳到headA即4第7步pA到0pB到1第8步pA到1ppB到8第9步pA到8pB到4p第10步pA到4ppB到5p第11步pA到5ppB到nullptrpB跳到headA第12步pA跳到headA即4pB到1第13步pA到1pB到8第14步pA到8pB到4p第15步pA到4ppB到5p第16步pA到5ppB到nullptrpB跳到headA第17步pA跳到headA即4pB到1 ……仔细数会发现这个例子里的A和B其实长度不同走法比较复杂。换个简单一点的例子更容易说明白设A的独占部分a2节点A1-A2B的独占部分b3节点B1-B2-B3公共部分c2节点C1-C2。pA走A1,A2,C1,C2然后到nullptr后跳到B1走B1,B2,B3再走C1此时到达C1。pB走B1,B2,B3,C1,C2nullptr后跳到A1走A1,A2再走C1也是到达C1。它们走的总步数都是7且都停在C1。当链表不相交时两个指针都会走完两个链表的所有节点同时到达nullptr此时pA和pB都为空循环结束返回空指针不会死循环。3. C实现细节打磨代码怎么写才不容易在面试现场翻车3.1 最精简的C解法样式双指针法的C实现可以非常短短到面试时两三行就把核心逻辑写完。这里给出我最常用的一版class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; } };这段代码的核心就是循环里的三目运算符如果当前指针不为空就向后移动一步为空就跳到另一个链表的头部。写法极度简洁但有一个隐患它没有显式处理headA和headB同时为nullptr的情况不过由于初始时pA pB nullptrwhile循环根本不会进入直接返回nullptr所以行为是正确的。3.2 逐行拆解为什么这样写更稳很多人的第一版代码不是上面这样写的而是用if判断while (pA ! pB) { if (pA nullptr) { pA headB; } else { pA pA-next; } if (pB nullptr) { pB headA; } else { pB pB-next; } } return pA;这个版本逻辑更清晰适合作为面试时的口头讲解版。三目运算符版本更简洁但我建议面试时优先用if版本因为它能展示你对边界条件的把控而不是炫技。两种版本的执行结果完全一致。我还有一个偏好指针变量名用pA和pB而不是a和b或pa和pb。在面试中手写代码时pA - pB的对称性一眼就能看出来你自己追溯逻辑的时候也更省力。别小看命名面试现场本来就很紧张命名越对称你讲起来越顺畅。3.3 关键细节为什么可以不判空直接返回这段代码最容易被问到的点是如果两个链表不相交pA和pB会不会一直互不相同导致死循环答案是不会。原因是两个指针走过的总步数一致。假设链表A长度为lenA链表B长度为lenB那么pA在遍历完lenA个节点后又遍历完lenB个节点总共经过lenA lenB个节点后变为nullptrpB也经过lenB lenA个节点后变为nullptr。两者成为nullptr的时机完全相同所以在pA ! pB这个条件中最终会出现pA和pB都为nullptr的情况此时循环条件不满足退出循环。还有一个细节容易被忽略当两个链表不相交且其中一个为空时while循环会不会误判假设headA为空而headB不为空初始pA nullptrpB headB条件pA ! pB成立进入循环。pA被赋值为headBpB向后走一步。这个行为乍一看有点奇怪但最终两个指针都会走完整条B链表再加上一条空链表然后在某一步同时变成nullptr退出循环返回nullptr结果正确。不过这种写法确实绕我建议在代码里加一个前置判空既清晰又不影响性能if (headA nullptr || headB nullptr) return nullptr;虽然不加也能得到正确答案但加上之后逻辑从第一行就非常顺面试官扫一眼就知道你考虑过空链表的边界。4. 边界场景专项排查空链表、不相交与其他刁钻输入4.1 空链表与单节点链表第一个边界场景是空链表。如果headA或headB为nullptr那么两个链表不可能相交应直接返回nullptr。这一点在双指针版代码中其实天然成立但如果面试官让你先讲思路你最好把空链表直接排除放在第一步讲而不是等代码写出来再说。第二个边界场景是单节点链表。两个单节点链表如果相交说明它们指向同一个节点对象也就是headA headB直接返回这个节点即可。如果它们各自指向不同节点则不相交返回nullptr。这段逻辑同样被双指针法自动覆盖但如果你先写计算长度差的版本就需要额外注意长度差为0时两个指针初始位置相同直接进入while循环判断不会出错。4.2 两个链表完全相同的情况当一个链表完全包含另一个链表比如链表A就是链表B的前半段那么两个链表在headA处就相交。这种情况下长度差版本的算法会让较短的链表指针先不动、较长的链表指针先走diff步然后两个指针从头开始同步走第一步就会相遇程序直接返回headA。双指针版本的算法则不关心谁长谁短它无条件地让两个指针走完两条链表最终自然在headA处相遇。我遇到过一种误判场景链表A和链表B相交后公共部分不是从相交点开始的所有节点而是中间某段共享后面又分开了。严格来说这不符合单向链表相交后必定完全重合的定义。单向链表的节点只有一个next指针两个链表一旦在某个节点相交之后的所有节点必然都是同一个对象序列无法再分离。所以看到相交后又分开的描述基本可以断定题目表述有误或者你对相交的理解有偏差。4.3 不相交链表与性能边界不相交的链表是双指针法最有意思的边界情况。之前提到过它们会在同时变为nullptr时退出循环返回nullptr。但这个过程中每个指针实际上都遍历了lenA lenB个节点。如果lenA 100000lenB 100000每个指针要走200000步整体时间复杂度依然是O(n m)没有额外空间消耗完全可以接受。我曾在一次自测中故意用两个长度悬殊且不相交的链表测试比如lenA 1lenB 100000。此时pA先走完A马上跳到B然后基本就是陪着pB把B走到头直到两者都变nullptr。整个过程没有报错也没有死循环性能在毫秒级。这说明只要理解总步数相同这一保证各种长度组合都在控制范围内。4.4 一个刁钻的输入相交节点在链表的最后一个节点有些测试用例会把相交节点设置为链表的最后一个元素。比如链表A [1,2,3]链表B [4,5,3]其中值为3的节点是同一个对象。这种情况下使用双指针法时两个指针会在最后一步同时走到这个节点然后返回。如果用长度差版本也是差多少走多少最后同步走到最后一个节点。这个边界并不特殊只是想提醒你不要假设两个链表一定在中间某个位置相交尾节点相交的情况是合法的。5. 从链表相交到环检测一道题的延伸思考5.1 双指针思想的统一视角链表相交的解法之所以经典不仅仅是因为它能用O(1)空间解决一个看似需要哈希表的问题更重要的是它展示了一种可迁移的思维通过补全长度的额外路径来把两个不同长度的遍历变成同步遍历。同样的思想换一个场景就变成了快慢指针判环。在环形链表中快指针每次走两步慢指针每次走一步它们总会相遇因为快指针相对慢指针以每次一步的速度逼近最终一定会追上。链表相交的双指针法和快慢指针法本质上是同一套同步移动数学相等性的思路只是应用的约束不同。如果你在面试中已经讲完链表相交的双指针解法面试官追问那怎么判断一个链表有没有环这时候你其实有了一个很好的衔接话术就和刚才的双指针类似不过这次是一个思路的变体让两个指针以不同速度走同一个链表。这种跨题目的联想能力往往比背十道题的代码更能打动面试官。5.2 实际开发中哪里会遇到链表相交检测很多人以为链表相交只是面试题现实工程中根本用不到。其实不然。我所知道的一个真实案例是某复杂系统的调试模块中使用了类似链表的对象引用链来记录资源依赖关系。当两个不同的资源引用链出现重叠时就说明存在共享子模块系统需要定位这个共享点来进行统一回收或缓存失效。这时候判断两个链表是否相交以及找到相交起始点就非常关键。还有一个场景是版本管理系统的对象图分析两个不同的变更序列可能共享同一个基础版本节点找出共享节点能帮助计算最小合并成本。当然工程中的链表往往不是教科书上那种单链表可能带有额外信息或双向指针但核心的双指针走两遍思路依然适用。这也是刷算法题的价值所在你未必会在业务代码里直接调用getIntersectionNode但你会经常遇到让两个不同序列对齐到同一个参考点这类问题。5.3 面试现场的讲解节奏建议根据我模拟面试的经验这道题最稳的讲解流程是先问清楚相交是指向同一个节点对象不是值相等。先说暴力法双重循环逐个比较O(n*m)时间O(1)空间太慢。再说哈希法O(nm)时间O(n)空间可以但不是最优。然后引出双指针先讲长度差消除版本再讲走两遍自动对齐版本说明后者代码更短且不需要预先遍历求长度。手动模拟一个小例子证明两个指针会相遇。说明边界空链表、不相交链表、都为空的情况。这套流程下来面试官基本能看到你的完整思考过程而不是背了一个答案。我在实际模拟面试中试过这个节奏效果很好最后一个问题基本都会变成如果链表有环会怎么样这种延伸讨论。关于这道题我个人刷了不下五遍每一遍都能找到新的理解角度。从最初背下代码到后来能推导出相遇的数学条件再到能把双指针思想迁移到其他问题中间经历的其实不是多刷题而是多问自己为什么。如果你也在准备技术面试我建议不要满足于把这段代码默写出来而是自己造几个链表例子把手动走一遍的过程写在纸上直到你能闭着眼睛说出pA走了lenAlenB步pB也走了lenBlenA步所以它们同时到nullptr或同时到交点这句话。做到这个程度面试官哪怕临时换个问法也难不倒你。
