链表相交问题：双指针法如何优雅消除长度差

1. 这道题到底在考什么160. 相交链表是链表专题里非常经典的一道题我在刷代码随想录链表章节时一度觉得它有点“绕”但搞明白之后发现它其实是链表题里思路最优雅的一类代表。先看题目本身的描述给你两个单链表的头节点headA和headB如果它们在某一个节点开始共享后续节点即相交请你找出并返回那个相交的起始节点如果两个链表不相交返回null。很多人第一次看到这道题会有一个误区以为“相交”是指两个节点的val相等或者两个链表有相同的后缀值。不是的这里说的相交是指针层面的相交也就是两个链表从某个节点开始后面的每一个节点在内存里都是同一个对象。打个比方两条路在某处汇合成一条路汇合之后的每一块路砖都是同一批砖而不是长得像的两批砖。这个区别非常重要因为它直接决定了题目的解法。如果只是值相等那可以用哈希表存值去重但指针相交意味着我们比较的是节点的“身份”而不是“长相”。代码随想录里把链表题按照“虚拟头节点”“双指针”“反转链表”等思路做了分类相交链表这题最适合归入双指针这一类而且它背后藏着一个非常漂亮的数学思想。理解了它你后面做环形链表、找链表中点、合并链表这些题都会有豁然开朗的感觉。适合谁来读这篇文章呢我觉得有这几类人刚刷完链表基础题想进阶理解双指针思想的同学面试前想快速梳理链表高频题的人自己写过这题但只背住了代码没真正搞懂原理的人。我会从题目分析、三种主流解法、Java 和 C 实现、常见坑以及如何举一反三这几个角度把这题彻底讲透。2. 题目拆解与核心难点2.1 相交的准确定义题目给了一个很关键的条件链表不能破坏原有结构而且相交判定是基于节点的引用/指针相等不是值相等。举个具体例子。假设有链表 Aa1 - a2 - c1 - c2 - c3链表 Bb1 - b2 - b3 - c1 - c2 - c3那么相交节点是c1因为从c1开始两个链表共用同一批节点。如果两个链表只是值的顺序恰好一样哪怕每个节点的val完全相同也不算相交——因为它们的内存地址不同。这个“身份 vs 长相”的区别也决定了判断条件应该写pA pB而不是pA.val pB.val。在实际面试中最容易犯的错误就是把写成.val相等然后越改越乱。2.2 直观解法为什么慢最容易想到的解法是暴力法拿链表 A 的每一个节点去链表 B 里从头遍历一遍看看有没有地址相同的。比如 A 长度 mB 长度 n时间复杂度就是O(m × n)。这个解法的思路很简单但代价也很明显一旦两个链表都有一万个节点就是一亿次比较在力扣的测试数据下大概率超时。更重要的是暴力法没有利用到“相交之后共享相同节点”这个隐含条件。另一个常见思路是哈希表把链表 A 的所有节点引用放进HashSet然后遍历链表 B逐个判断当前节点是否已经在集合里。这样做时间复杂度是O(m n)空间复杂度是O(m)能过题笔试时很稳妥。但面试官一般会追问一句“能不能把空间复杂度降到O(1)”这时候就需要双指针解法登场了。2.3 长度差问题的本质双指针解法的难点在于两个链表长度可能不一样如果两个指针同时从各自的头节点出发速度相同那么它们永远不可能同时到达相交节点——因为到达共同起点之前的“路程”不一样长。这就好比两个人从不同的地点出发速度一样却要在同一个地方碰头如果不做任何调整他们永远无法同步。所以问题的本质是如何消除两个链表从头到相交节点之间的长度差。只要解决了这个长度差让两个指针在“剩余路程”上对齐那么相交节点就会自然而然地被找到。3. 三种主流解法对比在动手写代码之前我先把三种思路放在一起做个对比方便你理解各自的适用场景。解法时间复杂度空间复杂度核心思路适用场景暴力双重循环O(m×n)O(1)每个 A 节点遍历整个 B仅用于理解题意不推荐哈希表法O(mn)O(m)先存 A 节点再查 B 节点笔试求稳思路简单双指针法O(mn)O(1)消除长度差后同步前进面试最优解必须掌握下面重点讲双指针法因为它是代码随想录里最推崇、也是我认为最优雅的解法。3.1 双指针法核心原理双指针法的思路是这样的让两个指针pA和pB分别从headA和headB出发每次各走一步。当pA走到链表 A 的末尾时把它重置到链表 B 的头节点继续走当pB走到链表 B 的末尾时把它重置到链表 A 的头节点继续走。如此循环直到两个指针相遇。为什么这样能相遇关键在于两个指针走过的总路程最终会相等。假设链表 A 不相交部分的长度为a链表 B 不相交部分的长度为b相交部分长度为c如果相交那么pA走过的完整路程 a c bpB走过的完整路程 b c a看出来了吗两者的总路程都是a b c。也就是说当pA走完链表 A 再去走链表 B 的不相交部分时pB恰好也走完了链表 B 再去走链表 A 的不相交部分。这时它们不仅在总路程上相等而且都处于“正在走对方链表的不相交部分”这个状态。如果两个链表相交那么等它们走完各自不相交的部分后就会在相交节点处相遇。如果不相交c 0它们最终都会走到null此时pA和pB都等于null循环退出返回null。这里有个特别精妙的地方不相交时两个指针在走完a b步后同时到达null这时候pA pB null我们不需要单独判断“是否相交”循环条件直接写while (pA ! pB)就够了。如果相等时是null就返回null如果是相交节点就返回那个节点。3.2 Java 实现基于上面的思路Java 代码非常简洁public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) { return null; } ListNode pA headA; ListNode pB headB; while (pA ! pB) { pA (pA null) ? headB : pA.next; pB (pB null) ? headA : pB.next; } return pA; } }这段代码我是按照代码随想录里的风格写的逻辑一目了然。需要注意几个细节先判空是必要的如果任一链表为空直接返回null避免后面空指针异常。三目运算符的写法要注意pA null时重置为headB而不是pA不动。很多人容易把方向搞反导致死循环。循环结束条件只有pA ! pB所以在循环内部不需要额外判断是否为空。3.3 C 实现C 版和 Java 版几乎没有差异class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return nullptr; ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; } };C 里唯一要注意的是判空写法用!headA和headA nullptr都可以看个人习惯。这类指针操作题在 C 里考察频率很高因为面试官想顺带看看你指针的基础是否扎实。3.4 Python 实现Python 版思路一致只是语法上更简洁class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: if not headA or not headB: return None pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pAPython 里有个小技巧pA pA.next if pA else headB这个写法比pA (pA None) and headB or pA.next清楚得多前者阅读起来语义明确后者容易踩到None判断的坑。4. 代码随想录的经典思路先对齐再遍历除了上面那种“边走边换”的双指针写法代码随想录里还有一种我认为更直观的思路——先计算两个链表的长度差让长链表先走几步然后两个指针同步出发。这种思路更像是在物理世界里的操作两个人要同时到达同一个地方那就先量出两个人的起点距离差让远的人先走一段然后两人保持相同速度前进。具体步骤如下分别遍历链表 A 和链表 B得到它们的长度lenA和lenB。计算长度差diff |lenA - lenB|。让长链表的指针先移动diff步此时两个指针对齐到“距离链表末尾相同距离”的位置。两个指针同步移动每走一步比较一次相等即返回如果走到末尾都没相等返回null。这个思路的代码实现如下Java 示例public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA getLength(headA); int lenB getLength(headB); // 让 pA 指向长链表的头pB 指向短链表的头 ListNode pA headA; ListNode pB headB; if (lenA lenB) { for (int i 0; i lenA - lenB; i) { pA pA.next; } } else { for (int i 0; i lenB - lenA; i) { pB pB.next; } } while (pA ! pB) { pA pA.next; pB pB.next; } return pA; } private int getLength(ListNode head) { int length 0; while (head ! null) { length; head head.next; } return length; } }两种做法在时间复杂度上都是O(m n)空间都是O(1)。差别主要在代码风格上“先对齐再遍历”的思路更贴近直觉适合在面试时向面试官解释你的思考过程。“边走边换”的代码更简洁少了一次完整遍历多了一点抽象性。我个人在面试时倾向于先说“先对齐再遍历”的思路讲清楚长度差问题然后写代码如果面试官要求优化代码长度再顺势切换到那种交换指针的写法。这样既展示了你的分析能力又展示了代码功底。5. 细节决定成败我在实际提交中踩过的坑这道题代码就十几行看起来简单但实际提交时会踩到的细节坑还真不少。我把自己的踩坑记录整理在这里希望你能绕开。5.1 判断条件到底该写什么我在初学的时候写出的第一版代码是这样的while (pA.val ! pB.val) { ... }这当然是错的原因前面讲过相交要比较的是节点地址而不是值。但还有一种“半错半对”的写法while (pA.next ! pB.next) { ... }这种写法在部分测试用例下能跑通但遇到链表只有一个节点时很容易出现空指针异常而且逻辑上也不严谨。正确写法永远是while (pA ! pB)直接比较指针本身。5.2 判空的顺序前面 Java 代码里我写了if (headA null || headB null) { return null; }千万别省掉这个判空。虽然双指针逻辑本身在链表为空的情况下也能正确返回null因为pA和pB都是null循环直接跳过返回pA也是null但加上判空的好处是语义清晰——你明确告诉读者两个链表只要有一个为空就绝对不可能相交。更重要的是在 C 里如果链表为空且没有判空pA-next这类操作会直接让程序崩溃而不是温和地返回错误结果。5.3 重置指针的时机在“边走边换”的双指针写法里有一个经典错误把重置逻辑写成这样。while (pA ! pB) { if (pA.next null) { pA headB; // 错误应该在 pA 为 null 时重置而不是 pA.next 为 null 时 } else { pA pA.next; } ... }看起来好像差不多但差别很大。正确写法是在pA已经走到null时才重置为headB而pA.next null时你还没离开链表 A 呢这时候强制换到链表 B会漏掉链表 A 的最后一个节点不仅结果可能错误还可能造成死循环。我建议你直接在代码里写三目运算符pA pA null ? headB : pA.next;这个写法从语义上就杜绝了上述错误。5.4 不相交时如何优雅退出很多人在处理不相交的情况时会额外加一个计数器超过某个步数就退出。其实没必要。因为双指针解法已经天然处理了不相交的情况两个指针最终都会到达null那时pA pB null循环自然结束。但有一点要特别注意如果两个链表不相交pA和pB会在某个时刻同时变成null吗答案是肯定的。因为它们走过的总路程都是a b此时c 0移动次数相同所以会同时到达各自链表的末尾。这就是这个解法最精妙的地方——不需要额外判断是否相交。6. 常见问题与易错点速查我把这类链表双指针题容易出错的地方统一整理成一张表刷题时拿出来对照很方便。问题类型错误示例正确做法原因比较对象pA.val pB.valpA pB相交比较的是节点身份而非值判空不判空直接遍历先判断任一链表为空则返回 null避免空指针异常语义更清晰重置时机pA.next null时重置pA null时重置确保最后一个节点被访问后再换链表循环结束条件额外计数器判断直接while (pA ! pB)不相交时两者会同时到 null天然退出长度差计算没有先遍历求长度先分别求 lenA 和 lenB必须知道长度差才能对齐起始位置这些坑我基本都踩过一遍尤其是第一种当时还觉得自己写得挺对跑测试用例却发现结果不对调试了好久才意识到是“值相等”和“节点相等”的区别。7. 从相交链表看大厂面试的套路刷题不能只刷一道题要有意识地把做法抽象成更通用的能力。相交链表这道题背后其实藏着好几个面试中高频出现的思维模式。7.1 双指针消除长度差这种“一个指针走到头就切换到另一个链表头”的思路本质上是一种循环接力。它不仅在相交链表中适用在判断链表是否有环时也可以借鉴——快慢指针实质上也是双指针的一种。掌握了这种思路后再遇到“两个链表找到第一个公共节点”“判断两个链表是否相交”之类的变形题基本就是秒解。7.2 环形链表的思维迁移有一个很近的类比142. 环形链表 II也是用双指针只不过这次是快慢指针。快指针每次走两步慢指针每次走一步如果链表有环它们一定会在环内相遇。找到相遇点后再用一个新的指针从头部出发与慢指针同步前进相遇处就是环的入口。这个过程和相交链表的核心逻辑非常相似——都是在用“路程相等”这个数学性质来定位特殊节点。所以刷完相交链表我强烈建议紧接着刷环形链表你会感受到那种“一通百通”的快感。7.3 面试中如何描述解法面试官让你讲思路时不要直接背代码而是用讲故事的方式说“我让两个指针同时出发速度一样。如果两个链表长度相同它们会同时到达第一个公共节点。但长度可能不同所以当一个指针走完自己的链表后就让它去走另一个链表。这样一来两个指针在到达公共节点之前走过的总路程就一样了于是它们必然会在公共节点相遇。”这个解释有几层意思你理解了问题的本质是长度差你知道用数学方式消除长度差你能把抽象逻辑转化为自然语言。这几层正好是面试官在考察的点。8. 扩展如何自己构造相交链表的测试用例在实际开发或自己练习时我们经常需要构造测试数据而不是只在力扣上跑题。我分享一个快速构造相交链表的 Python 代码class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def buildIntersectedList(): # 公共节点部分 common ListNode(8) common.next ListNode(10) common.next.next ListNode(12) # 链表 A1 - 2 - 3 - common headA ListNode(1) headA.next ListNode(2) headA.next.next ListNode(3) headA.next.next.next common # 链表 B9 - common headB ListNode(9) headB.next common return headA, headB这样构造出来的两个链表相交节点就是common。你可以用它配合调试工具打日志观察每一步的指针变化。对于还在学习阶段的朋友我也建议在本地打印每一步pA和pB的地址值你会非常直观地看到它们是如何一步一步靠近彼此的。9. 进一步的思考为什么链表题这么重要链表是算法面试中的一个高频考点但它的代码量往往不大考察的更多是思维严密性和细节处理能力。相交链表这道题尤其如此——十几行代码里浓缩了“指针操作”“边界处理”“数学证明”三种能力。在刷题初期我一度觉得链表比数组难理解因为数组只要按下标访问就行了链表却总在 “next” 和 “空指针” 之间游走。但后来我发现链表的题目难度不在语法而在你把整个过程抽象成什么样的模型。用生活类比来说数组就像一排编好号的储物柜你知道每个柜子的位置链表则像一条寻宝路线你只知道当前脚下的这个盒子盒子里面写着下一个盒子的位置。相交链表这道题就是在两条寻宝路线中找它们重合的那一段。理解了这个类比再看代码里的pA和pB就不会觉得抽象了。回到题目本身无论是代码随想录里的“先对齐再遍历”还是我前面提到的“边走边换”本质上都指向同一个结论对于两条可能相交的链表用双指针走完彼此的全程它们总会在相交点相遇如果没有相交点它们会在彼此的终点相遇那个终点就是null。我个人在实际做题中的体会是不要满足于把题刷过更要把思路讲给自己听一遍。如果你能在不看代码的情况下完整地解释清楚为什么双指针最终会相遇以及为什么不相交时也不会死循环那说明你是真的会了。反之如果你只是把代码背了下来面试时一紧张就很容易在pA null ? headB : pA.next这种细节上把自己绕进去。刷题没有捷径但每一个“我为什么这么写”的问题都会在未来某个面试现场帮你省下关键的几分钟。