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

刷题的人都绕不开 LeetCode Hot100，这套题单基本把面试里最高频的算法考点都覆盖了。Hot100 第十二题“相交链表”，题面很短，描述也不复杂，但很多人第一次遇到时反而容易懵：两个链表怎么就算相交了？相交之后怎么找那个节点？用暴力一定能做，但面试官想听的显然不是暴力。这道题真正想考察的，是你对链表节点指针的理解，以及能不能优化到线性时间、常数空间。这篇就围绕这道题把思路、原理、代码和踩坑点完整捋一遍，适合正在刷 Hot100、准备面试或者想补链表基础的读者。

LeetCode 原题编号是 160，题目名字叫 Intersection of Two Linked Lists，Hot100 里排在第 12 位。这道题的经典程度不用多说，解法也很多，但最漂亮的还是那个双指针互相走一圈的思路。别急着背代码，先搞清楚它为什么能成立，后面你写起来才不会心虚。

1. 先把题目真正读懂

1.1 题目描述和示例

题目给了两个单链表的头节点 headA 和 headB，要求找到两个链表相交的起始节点。如果两个链表没有交点，返回 null。题目还有一个隐含要求，也是面试里常见的硬性条件：时间复杂度 O(m+n)，空间复杂度 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_set（C++）或者 HashSet（Java），再遍历链表 B，只要某个节点指针能在集合里找到，那这个节点就是相交节点，直接返回；如果遍历完 B 都没找到，说明没有交点，返回 null。

这个思路比暴力法清晰很多，时间复杂度降到 O(m+n)，因为建集合需要 O(m)，查链表 B 需要 O(n)。空间复杂度是 O(m)，需要额外的哈希表来存链表 A 的节点。

3.2 哈希法的关键代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> 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_set<ListNode*>，存的是指针而不是节点值。你可能会问，为什么不用 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。这样两个指针都遍历了 m+n 个节点，最终会在相交节点相遇。

文字描述比较抽象，用实际例子演示一下。链表 A 长度为 5，链表 B 长度为 3，相交节点是 c1：

A: a1 -> a2 -> a3 -> c1 -> c2 B: b1 -> b2 -> c1 -> c2

pA 的路径是 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 步到 c1，pB 也走了 5 步到 c1，它们走的总长度分别是 m+(n-相交前部分长度) 和 n+(m-相交前部分长度)，相等，所以会同时到达交点。

4.2 为什么两个指针一定会相遇

这一步是很多人的盲区。背代码容易，但面试时被问“为什么这样不会死循环？为什么能保证相遇？”就卡壳了。

分两种情况讨论。

第一种，链表 A 和链表 B 有交点。设链表 A 不相交的部分长度为 a，链表 B 不相交的部分长度为 b，公共部分长度为 c。pA 从 headA 出发走完链表 A（长度 a+c），然后从 headB 继续走，走到相交节点需要再走 b 步，所以 pA 走到交点时总共走了 a+c+b 步。pB 从 headB 出发走完链表 B（长度 b+c），然后从 headA 继续走，走到相交节点需要再走 a 步，总共走了 b+c+a 步。这两个表达式相等，都是 a+b+c，所以 pA 和 pB 必然在交点相遇。注意，这里的“交点”是它们第一次指针相等的位置，不一定非要是同一个节点在各自原始链表中的位置，但根据路径推导，就是在相交节点。

第二种，链表 A 和链表 B 没有交点。pA 走完链表 A 再走链表 B，总共走 m+n 步；pB 走完链表 B 再走链表 A，也总共走 m+n 步。当它们都走到最后一步时，pA 等于 null，pB 也等于 null，两个 null 是相等的，循环结束，返回 null。这也印证了为什么循环条件可以写成while (pA != pB)，因为无交点时最终都会变成 null，null == 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 pA

Python 里特别要注意一点：比较两个节点必须用is，不能用==。Python 的==会调用对象的__eq__方法，ListNode 默认没重写这个方法，所以==实际比较的是内存地址，碰巧也能用。但为了避免依赖默认行为，更严谨的写法是用is比较身份。写 C++ 的时候也有类似的注意点，比较指针用==没问题，因为 C++ 的指针==比较的是地址，天然正确。Python 里is not才是语义明确的做法。

4.4 复杂度与对比总结

双指针法的时间复杂度是 O(m+n)，因为每个指针最多走过 m+n 个节点。空间复杂度是 O(1)，只用了两个指针变量。这个方案同时满足题目的两个硬性要求，也是面试官最希望听到的最终答案。

三种解法放在一起看会更加清晰。暴力法时间复杂度 O(m*n)，空间 O(1)；哈希法时间复杂度 O(m+n)，空间 O(m)；双指针法时间复杂度 O(m+n)，空间 O(1)。从暴力到哈希再到双指针，其实就是一个层层优化的过程。面试时即使一开始没想到双指针，能顺着这条路径提示写出最优解，也是完全能够得高分的。

5. 常见错误与调试技巧

5.1 高频错误速查表

这道题的代码量很小，但错误点却不少。我在力扣评论区见过不少经典错误，自己也踩过几个，整理成一张表：

第一行是绕不开的认知坑。初学者很容易被样例带偏，看到样例里相交节点值相同就以为比较数值就行。实际上一旦构造出值相同但不相交的两个链表，这种写法就直接挂了。力扣的判题器构造测试用例时，节点地址是不一样的，只有真正共享节点才叫相交。

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 走完自己的 m+c 步后再去走对方的 b 步，和 pB 走完 n+c 步后再去走对方的 a 步，两者总步数都是 a+b+c，所以必然相交节点相遇”，这道题才算真正吃透了。Hot100 里比这更难的题还有很多，但这类“答案很短原理很深”的经典题，往往才是面试中最容易拉开差距的地方。