LeetCode 160 相交链表：双指针解法与原理详解

刷题的人都绕不开 LeetCode Hot100这套题单基本把面试里最高频的算法考点都覆盖了。Hot100 第十二题“相交链表”题面很短描述也不复杂但很多人第一次遇到时反而容易懵两个链表怎么就算相交了相交之后怎么找那个节点用暴力一定能做但面试官想听的显然不是暴力。这道题真正想考察的是你对链表节点指针的理解以及能不能优化到线性时间、常数空间。这篇就围绕这道题把思路、原理、代码和踩坑点完整捋一遍适合正在刷 Hot100、准备面试或者想补链表基础的读者。LeetCode 原题编号是 160题目名字叫 Intersection of Two Linked ListsHot100 里排在第 12 位。这道题的经典程度不用多说解法也很多但最漂亮的还是那个双指针互相走一圈的思路。别急着背代码先搞清楚它为什么能成立后面你写起来才不会心虚。1. 先把题目真正读懂1.1 题目描述和示例题目给了两个单链表的头节点 headA 和 headB要求找到两个链表相交的起始节点。如果两个链表没有交点返回 null。题目还有一个隐含要求也是面试里常见的硬性条件时间复杂度 O(mn)空间复杂度 O(1)m 和 n 分别是两个链表的长度。先看一个典型例子。链表 A 是 a1 - a2 - c1 - c2 - c3链表 B 是 b1 - b2 - b3 - c1 - c2 - c3。那么从 c1 开始两个链表就是同一个链表了c1 就是相交节点。直观上可以想象成两个链表从某个点开始合并成一条路像两条溪流汇成一条河。有个容易混淆的点是“相交”的定义。题目假设链表是无环的两个链表相交后的部分完全共享同一批节点而不是“数值相同”。相交的判断标准是节点的地址相同也就是指针相等而不是节点里存的值相等。这一点特别重要等会讲代码的时候你更能体会到。1.2 为什么这道题值得单独拿出来反复做单看题目本身确实不难但它的价值在于一题多解。暴力法、哈希法、双指针法三种解法的时间空间复杂度各不相同恰好能体现算法优化的完整路径。面试官特别喜欢拿这道题来考察候选人的思考过程先给一个能跑的方案再引导你逐步优化最后看你能不能写出双指针版本。我自己刷了三遍这道题每一遍都有新的体会。第一遍看题解觉得双指针很神奇背下来了第二遍自己推演证明过程才明白原理第三遍在面试中遇到相似变体能直接迁移思路。很多人觉得 LeetCode 记住题解就够了其实真正拉开差距的是你能不能独立推导、能不能用这个思路解决新问题。2. 解法一暴力双重循环能过但不够好2.1 暴力思路其实很直观最直接的思路是枚举链表 A 的每一个节点然后遍历链表 B看有没有节点和它相同。这种双重循环的做法时间复杂度是 O(m*n)空间复杂度是 O(1)。在小规模测试用例上确实能 AC但遇到长链表就明显慢面试时如果第一反应就给这个解法面试官大概率会追问“能不能更快”。很多同学觉得暴力解法没有价值不屑于提。但我不这么看。暴力解法是思考的起点它把题目翻译成最朴素的逻辑两条链表相交必然有一个公共节点那我逐个比对就好了。有了这个最朴素的方案后面才谈得上优化。面试中主动提一句“我先把暴力解法说清楚再讨论优化方向”往往能给面试官留下好印象。2.2 暴力法的代码与复杂度参考ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA headA; while (pA) { ListNode *pB headB; while (pB) { if (pA pB) return pA; pB pB-next; } pA pA-next; } return nullptr; }注意这里比较的是pA pB也就是指针地址相等而不是pA-val pB-val。举个例子链表 A 有一个节点值是 5链表 B 也有一个节点值是 5但这两个节点是在内存里不同地方创建的它们不是同一个节点。如果两个链表只是某个位置的值相同不代表它们相交了。复杂度也说明这个方案的问题最坏情况下要比较 m*n 次两个长度都是 10^4 的链表就是一亿次比较跑起来已经有明显延迟。如果链表长度到 10^5完全不可接受。所以暴力法只适合作为思维起点不适合作为最终方案。3. 解法二哈希集合时间和空间的平衡3.1 用哈希表记录链表 A 的节点暴力法慢在每次比较都要重新遍历整条链表 B那能不能把链表 A 的节点先存下来然后遍历链表 B 的时候直接查哈希集合就是干这个的。先把链表 A 的所有节点指针放进一个 unordered_setC或者 HashSetJava再遍历链表 B只要某个节点指针能在集合里找到那这个节点就是相交节点直接返回如果遍历完 B 都没找到说明没有交点返回 null。这个思路比暴力法清晰很多时间复杂度降到 O(mn)因为建集合需要 O(m)查链表 B 需要 O(n)。空间复杂度是 O(m)需要额外的哈希表来存链表 A 的节点。3.2 哈希法的关键代码ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* visited; ListNode *pA headA; while (pA) { visited.insert(pA); pA pA-next; } ListNode *pB headB; while (pB) { if (visited.count(pB)) return pB; pB pB-next; } return nullptr; }这里用unordered_setListNode*存的是指针而不是节点值。你可能会问为什么不用 unordered_set 存值因为链表节点可能有重复值而且相交的定义是地址相同单纯存值会产生误判。比如链表 A 有一个节点值是 7链表 B 也有一个节点值是 7但它们内存地址不同如果按值存就会错误地认为相交了。这一点是哈希解法里最容易踩的坑。哈希法面试时也可以给属于中规中矩的答案。面试官会说“思路没问题能不能把空间优化到 O(1)”这时候就该双指针上场了。4. 解法三双指针互相“串门”的经典思路4.1 核心想法消除长度差先思考一个问题如果两条链表一样长那从 headA 和 headB 同时出发各自用一个指针一步一步走第一个指针相等的节点就是相交节点对不对因为长度相同两个指针会同时到达相交位置。如果链表 A 比链表 B 长 k 个节点那就让链表 A 的指针先走 k 步然后再同步走也能同时到达相交位置。但是题目要求 O(1) 空间而且不能修改链表。有没有办法在不额外记录长度的情况下消除长度差双指针的做法非常巧妙pA 从 headA 出发pB 从 headB 出发两个指针每次都向后走一步。当 pA 走到链表 A 末尾时把它重定向到 headB当 pB 走到链表 B 末尾时把它重定向到 headA。这样两个指针都遍历了 mn 个节点最终会在相交节点相遇。文字描述比较抽象用实际例子演示一下。链表 A 长度为 5链表 B 长度为 3相交节点是 c1A: a1 - a2 - a3 - c1 - c2 B: b1 - b2 - c1 - c2pA 的路径是 a1 - a2 - a3 - c1 - c2 - null - b1 - b2 - c1。pB 的路径是 b1 - b2 - c1 - c2 - null - a1 - a2 - a3 - c1。当 pA 走到 c2 后跳到 b1此时 pB 也走完了自己的链表跳到 a1两者在第二轮中同步前进最终在 c1 相遇。关键在于pA 总共走了 7 步到 c1pB 也走了 5 步到 c1它们走的总长度分别是 m(n-相交前部分长度) 和 n(m-相交前部分长度)相等所以会同时到达交点。4.2 为什么两个指针一定会相遇这一步是很多人的盲区。背代码容易但面试时被问“为什么这样不会死循环为什么能保证相遇”就卡壳了。分两种情况讨论。第一种链表 A 和链表 B 有交点。设链表 A 不相交的部分长度为 a链表 B 不相交的部分长度为 b公共部分长度为 c。pA 从 headA 出发走完链表 A长度 ac然后从 headB 继续走走到相交节点需要再走 b 步所以 pA 走到交点时总共走了 acb 步。pB 从 headB 出发走完链表 B长度 bc然后从 headA 继续走走到相交节点需要再走 a 步总共走了 bca 步。这两个表达式相等都是 abc所以 pA 和 pB 必然在交点相遇。注意这里的“交点”是它们第一次指针相等的位置不一定非要是同一个节点在各自原始链表中的位置但根据路径推导就是在相交节点。第二种链表 A 和链表 B 没有交点。pA 走完链表 A 再走链表 B总共走 mn 步pB 走完链表 B 再走链表 A也总共走 mn 步。当它们都走到最后一步时pA 等于 nullpB 也等于 null两个 null 是相等的循环结束返回 null。这也印证了为什么循环条件可以写成while (pA ! pB)因为无交点时最终都会变成 nullnull null循环自然退出不需要额外标记。还有一个小细节值得想清楚为什么不会出现 pA 和 pB 一直追不上、死循环因为两个指针的总步数最终是一样的要么在交点前相遇要么同时触及 null不存在无限循环的可能。这个“互相交换路径”的设计保证了步数的一致性。4.3 双指针的最终代码ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return nullptr; ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }这里有个写法细节值得留意。很多人会写成这样pA pA-next ? pA-next : headB;这个写法有个问题如果 pA 已经为空再访问 pA-next 就是操作空指针了。所以更稳妥的写法是先判断 pA 本身是否为空。上面的代码用pA pA ? pA-next : headB就避免了空指针解引用。虽然这道题链表没有环正常情况不会出问题但养成判空的习惯没坏处。Python 版本也很简洁class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]: 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 pAPython 里特别要注意一点比较两个节点必须用is不能用。Python 的会调用对象的__eq__方法ListNode 默认没重写这个方法所以实际比较的是内存地址碰巧也能用。但为了避免依赖默认行为更严谨的写法是用is比较身份。写 C 的时候也有类似的注意点比较指针用没问题因为 C 的指针比较的是地址天然正确。Python 里is not才是语义明确的做法。4.4 复杂度与对比总结双指针法的时间复杂度是 O(mn)因为每个指针最多走过 mn 个节点。空间复杂度是 O(1)只用了两个指针变量。这个方案同时满足题目的两个硬性要求也是面试官最希望听到的最终答案。三种解法放在一起看会更加清晰。暴力法时间复杂度 O(m*n)空间 O(1)哈希法时间复杂度 O(mn)空间 O(m)双指针法时间复杂度 O(mn)空间 O(1)。从暴力到哈希再到双指针其实就是一个层层优化的过程。面试时即使一开始没想到双指针能顺着这条路径提示写出最优解也是完全能够得高分的。5. 常见错误与调试技巧5.1 高频错误速查表这道题的代码量很小但错误点却不少。我在力扣评论区见过不少经典错误自己也踩过几个整理成一张表错误表现根本原因正确做法比较节点值而非指针把“相交”理解成“值相等”用 pA pB 比较指针地址空链表时报错没处理 headA 或 headB 为空的情况开头判空直接返回 nullptr双指针跳转时死循环跳转逻辑写成 pA-next ? pA-next : headB正确写法是 pA ? pA-next : headB哈希集合存值导致误判用 unordered_set 存节点值必须存 ListNode* 指针误以为需要求长度拿到题想先遍历计数再对齐双指针法不需要显式求长度但暴力法求长度也是一种可行思路第一行是绕不开的认知坑。初学者很容易被样例带偏看到样例里相交节点值相同就以为比较数值就行。实际上一旦构造出值相同但不相交的两个链表这种写法就直接挂了。力扣的判题器构造测试用例时节点地址是不一样的只有真正共享节点才叫相交。5.2 调试时怎么排查指针问题链表题调试起来比数组题麻烦因为链表节点在内存里是离散的你没法像看数组一样直观地看到全部元素。我调试这道题时常用的方法是在关键位置打印节点地址或者指针值。写个简单的调试版本在双指针跳转前后打印当前指针对应的节点值可以快速发现问题while (pA ! pB) { printf(pA%p val%d, pB%p val%d\n, pA, pA ? pA-val : -1, pB, pB ? pB-val : -1); pA pA ? pA-next : headB; pB pB ? pB-next : headA; }%p打印的是指针地址如果两个指针的地址逐渐靠近、最后相等就说明逻辑在按预期收敛。如果打印了几十行都没有相等迹象那基本可以确定跳转逻辑或者循环条件写错了。打印的时候记得处理 pA 或 pB 为空的情况否则空指针访问 val 直接崩掉。另外可以自己构造一个简单的相交链表来测试不要一上来就提交。我经常在本地用循环构造两条有交点的链表然后跑三个解法对比输出确保结果一致。手工测试的用例要覆盖有交点且长度相同、有交点且长度不同、无交点、其中一个为空链表这四种情况都能通过才算稳。6. 面试现场和后续延伸6.1 这道题面试官到底想考什么从面试官的角度看这道题不是单纯考你会不会背双指针代码而是看你能不能展示完整的思考链路。我参加过不少模拟面试总结下来面试官通常这样引导先让你说思路然后追问“你的时间复杂度是多少空间复杂度呢能不能优化”如果你一开始就给暴力法也别慌回答完复杂度后主动说“我想到可以用哈希集合优化时间”再进一步说“空间也可以优化到常数我有思路是用双指针”整个思路递进本身就说明你有算法直觉。还有一个常见的引导是如果链表可能有环这道题还能用双指针吗这个问题把“相交链表”和“环形链表”联系起来考的是知识迁移能力。有环的情况下不能直接用原双指针需要先用快慢指针判断是否有环并找到环入口再做处理。你不需要当场给出完整答案但至少能说出“有环会让指针走入死循环得先处理环”这个方向就已经超出平均水平了。6.2 题单刷到这里应该形成的方法论Hot100 做到第 12 题正好是建立链表解题感觉的关键时期。链表题有一个共性很多题都是指针操作的变体。反转链表是改 next环形链表是快慢指针相交链表是双指针同步走回文链表是先找中点再反转后半段。把这些题串起来看你会发现底层的操作模式其实高度一致通过控制指针的前进节奏和方向在链表上完成特定逻辑。具体到这道题学会的是“两个指针走完自己的路再去走对方的路”这种互相补足的思想。这个套路不只是链表题能用很多双指针问题也有相似逻辑。所以我不建议只背代码把证明过程写一遍、把三种解法的复杂度分析一遍再找两三个变体题练习效果比盲目刷二十道新题更好。6.3 可能的变体与扩展方向这道题的变体不会太复杂但确实有人考。面试官可能会问如果题目改成“返回两个有序单链表的第一个公共值节点”值相等就算解法就完全不一样了因为有序链表可以用归并的思路比较不需要哈希或双指针换路。这个变体本质上考察的是你能不能识别出对比条件从“指针相等”变成“值相等”时解题路径会变化。另一种变体是“求两个相交链表的公共部分长度”这时候可以先找到相交节点然后分别从头遍历到相交节点计数答案就是两个计数的和减去公共部分长度。或者直接问“如何在 O(1) 空间内判断三条链表中哪两条相交”思路会转到两两组合用哈希法比较。面试时碰到这些变形核心还是底层原理是否扎实。我自己刷 Hot100 的经验是每一道题都要能回答三个问题暴力解法是什么最优解法的每一步为什么成立空间换时间或者时间换空间的取舍在哪里相交链表这道题就是最典型的例子从暴力到哈希再到双指针三座台阶正好对应这三个问题。最后分享一个刷题时的小技巧把这道题的双指针解法写在纸上不看任何参考自己推导一遍 pA 和 pB 的行走路径然后口头解释为什么它们能相遇。这个动作看起来简单但比在编辑器里复制粘贴代码有用得多。等到面试时能流利地讲出“pA 走完自己的 mc 步后再去走对方的 b 步和 pB 走完 nc 步后再去走对方的 a 步两者总步数都是 abc所以必然相交节点相遇”这道题才算真正吃透了。Hot100 里比这更难的题还有很多但这类“答案很短原理很深”的经典题往往才是面试中最容易拉开差距的地方。