LeetCode 160 相交链表：双指针、哈希表与链表算法详解

1. 项目背景与题目核心解析

1.1 这道题为什么值得认真刷三遍

如果你刷过 LeetCode，大概率绕不过编号 160 的"相交链表"（Intersection of Two Linked Lists）。这道题在面试题里出现频率极高，很多大厂的技术面、二面甚至笔试环节都会用到，尤其是偏向底层数据结构和算法基础的岗位，链表操作几乎属于必考范围。

我第一次接触这道题的时候，第一反应是："这不就是遍历两个链表，然后找第一个相遇的节点吗？"但真上手去写，就会发现事情没那么简单：如果直接暴力比对，时间复杂度轻松到 O(mn)，数据量一大就废了；如果单纯用哈希表，能过但不够优雅；真正让面试官点头的方案，往往是双指针解法——它的思维模式和链表操作习惯，才是这道题真正要考的东西。

这道题的内容可以这么理解：有两个单链表，它们从某一个节点开始合并，之后的所有节点都共享同一条路径，你需要找出这个"第一个相交节点"。如果没有任何相交，则返回 null。链表的结构决定了我们不能像数组那样随机访问，所以题目既考对链表操作的理解，又考你对"空间复杂度和时间复杂度的权衡能力"。

1.2 题目描述和常见的理解偏差

先看一道典型描述：给定两个单链表 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

很多人理解这道题时，容易把 "节点值相同" 和 "节点地址相同" 搞混。链表相交，指的是两个链表中的某个节点是同一个对象，也就是说它们在内存里的地址一致，而不仅仅是数值相等。这一点是题目设计的核心陷阱。我见过有人在代码里用p.val == q.val来判断相遇，结果就是测试数据里面一堆相同数值的节点，直接错得一塌糊涂。

它的整体结构是这样：链表 A 可能是{4, 1, 8, 4, 5}，链表 B 是{5, 6, 1, 8, 4, 5}，它们在值为 8 的节点处相交，后面的节点是共享的。但注意，值为 1 的节点虽然两个链表里都有，但它不是交点，因为节点地址并不相同。

2. 三种主流实现方案及原理详解

2.1 哈希表法：最容易想到的暴力进阶版

哈希表方案大概是所有解法里最容易理解的。思路是：遍历链表 A，把每个节点的引用（Java 里是ListNode对象的地址）存进一个 Set；然后遍历链表 B，第一次检测到某个节点已经存在于 Set 中，说明这就是交点；如果遍历完整个链表 B 都没有命中，则两个链表不相交。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> visited = new HashSet<>(); ListNode temp = headA; while (temp != null) { visited.add(temp); temp = temp.next; } temp = headB; while (temp != null) { if (visited.contains(temp)) { return temp; } temp = temp.next; } return null; }

这个方案的时间复杂度是 O(m + n)，空间复杂度是 O(m)（或者 O(n)，看把哪个链表存进去了）。为什么说它是"暴力进阶版"？因为它在时间复杂度上已经达标了，只是额外开了一个哈希表来存储节点引用，空间上稍微吃亏。面试时你可以把哈希表方案作为第一反应说出来，然后自然过渡到双指针方案，这样展示的是一个由易到难的思考过程，而不是死记硬背标准答案。

注意：这里的 Set 存的是节点的内存引用，不是节点的 val。如果只存 val，遇到重复值就会误判。

2.2 双指针法：让两个指针走同样的总长度

双指针法是这道题的高频标准答案。核心思想是：定义两个指针 pA 和 pB，分别从 headA 和 headB 出发。只要两个指针不为 null，就各自向后移动一步。当 pA 走到链尾时，把它移到 headB 继续走；当 pB 走到链尾时，把它移到 headA 继续走。如果两个链表相交，那么两个指针最终会同时到达交点；如果链表不相交，两个指针会在同时走到 null 的时候结束。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode pA = headA, pB = headB; while (pA != pB) { pA = (pA == null) ? headB : pA.next; pB = (pB == null) ? headA : pB.next; } return pA; }

为什么这个方案能成立？我用一个生活化的类比来解释：假设两条跑道从某个汇合点开始合并成一条跑道，两个运动员分别从两条跑道的起点出发，速度相同，但一个人在前面一段单独跑，另外一个人在另一段单独跑。为了让他们能同时站在同一个汇合点，我们需要让跑的路径总长度一致。双指针的做法本质上是让两个指针各自走完自己的链表之后，再去走对方的链表，这样总路径长度就变成了 m + n，两个指针走过的总路程一样，最终一定同时到达交点或者同时走到终点。

更严谨一点说：如果相交，设交点前链表 A 的长度为 a，链表 B 的长度为 b，公共段长度为 c。那么指针 pA 走 a + c + b 步到达交点（从链表 A 走到交点，然后切换去走链表 B 的剩余部分），指针 pB 走 b + c + a 步到达交点。由于 a + c + b = b + c + a，它们必然在交点相遇。如果不相交，则两个指针各自走完 m + n 步后同时为 null，退出循环。

2.3 长度差法：先对齐尾端再找交点

长度差法的逻辑更直观，理解起来门槛更低。先分别遍历两个链表，统计它们的长度，记为 lenA 和 lenB。然后让较长的链表的指针先向前走lenA - lenB步（假设 A 长），这样两个指针距离链表尾部的距离就一样了。接下来两个指针同步前进，每次比较两个指针指向的节点是不是同一个，是就返回该节点；都走到了 null 还没遇到相同节点，就返回 null。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = getLength(headA); int lenB = getLength(headB); ListNode pA = headA, pB = headB; while (lenA > lenB) { pA = pA.next; lenA--; } while (lenB > lenA) { pB = pB.next; lenB--; } while (pA != pB) { pA = pA.next; pB = pB.next; } return pA; } private int getLength(ListNode head) { int len = 0; while (head != null) { len++; head = head.next; } return len; }

这个方案理解起来最贴近人的直觉：既然两个链表有公共尾部，把链表按照尾端对齐后，交点前面的节点数量就一样了，那么同步往后走就一定能同时找到交点。空间复杂度是 O(1)，时间复杂度也是 O(m + n)，因为长度统计和后续的遍历都是线性级别。

要说它和双指针法的区别，我认为最大差异在于：长度差法需要额外遍历链表统计长度，整体代码流程更"直译"题目结构；双指针法则不需要知道具体长度，靠指针切换自然完成对齐。两者面试里都能用，但从简洁程度上说，双指针法往往更受考官欣赏。

3. 边界条件、链表示例与特殊情况处理

3.1 空链表和单节点的处理逻辑

任何链表算法题，第一道坑永远是空指针。如果 headA 为 null 或者 headB 为 null，直接返回 null，这是题目要求，也是防御性编程的基本习惯。代码里如果不先做判空，后面所有的.next操作都可能触发NullPointerException，这在线上跑测试用例的时候会很难看。

另外，单节点相交的情况也一样要能处理。比如链表 A 只有{1}，链表 B 也只有{1}，并且这个节点是同一个引用，那么三个方案都能正确返回这个节点。但如果两个链表都只有一个节点，而这两个节点是不同的对象，返回 null 也是正确行为。这里本质还是"引用是否相等"，不是"值是否相等"。

3.2 有交点但长度差距很大的情况

举一个极端样例：链表 A 有 100 个节点，链表 B 只有 3 个节点，第 3 个节点就是交点。这种情况下哈希表法完全没问题；长度差法会让链表 A 的指针先走 97 步，然后两个指针只要再走 1 步就能命中交点；双指针法会走 100 + 3 + 公共段长度，虽然步数多一些，但依然是线性级别。

还有一种情况是交点正好在链表结尾，也就是两个链表只有最后一个公共节点。这种情况下，三种方案都能正确返回最后一个节点。还有一种情况是其中一个链表是另一个链表的完整前缀，比如链表 A 全部包含在链表 B 中，并且链表 A 的最后一个节点就是交点。这类边界数据对双指针法和长度差法来说都是顺路验证逻辑的场景，不用担心。

3.3 无交点时怎么保证不超时

双指针法最容易被质疑的点就是："如果两个链表根本不相交，你的指针会不会死循环？"答案是不会。因为两个指针都走了 m + n 步之后，都会变成 null，循环结束。而长度差法更直接：两个指针同步走完尾部，同时为 null，循环自然结束，根本不存在死循环的可能。

我在练习时特意构造过两个完全不相交但长度相同的链表来测试，双指针的逻辑是：pA 走到 null 后切到 headB，pB 走到 null 后切到 headA，最后两者同时为 null 退出，返回 null。整个流程最多多走一遍，不会超时，也不会内存溢出。

4. 完整实战过程：从读题到提交通过的逐步复盘

4.1 准备测试用例与本地调试环境

我在本地练习时，并不会直接打开 LeetCode 页面写代码，而是习惯先在本地编辑器里把链表的构造、输出函数写好，这样可以快速验证核心逻辑。这里写一个简单的测试框架，方便你直接跑：

public class LinkedListTest { public static void main(String[] args) { ListNode common = new ListNode(8); common.next = new ListNode(4); common.next.next = new ListNode(5); ListNode headA = new ListNode(4); headA.next = new ListNode(1); headA.next.next = common; ListNode headB = new ListNode(5); headB.next = new ListNode(6); headB.next.next = new ListNode(1); headB.next.next.next = common; ListNode result = new Solution().getIntersectionNode(headA, headB); System.out.println(result == null ? "null" : result.val); } }

注意我这里构造的公共链表是一个单独创建的ListNode(8)对象，然后让两个链表在各自的某个节点上指向它。这样才能真正模拟内存地址相同的相交节点，而不是仅仅把 val 设置成一样的 8。很多人测试时偷懒，直接新建两个链表，在每个节点都new ListNode(8)，这样节点地址不同，程序自然输出 null，然后开始怀疑算法写错了。

4.2 提交时容易踩的编译与边界问题

LeetCode 默认给出的方法签名只能改方法体内部，不能随便改函数返回值类型或参数类型。我在实际提交时遇到过这样的情况：想顺便返回一个布尔值表示"是否相交"，结果因为返回类型写错导致编译失败。正确的做法是保持ListNode返回类型，相交返回节点对象，不相交返回null。

另外还有一个小细节：有些语言里如果两个链表没有交点，需要返回None而不是null，这本身没问题，但要小心自定义测试用例写判断的时候不要写result == null，因为 Python 的None和 Java 的null在语义上等价，但在你的本地测试函数里要匹配正确。

4.3 性能对比与实测数据

我跑了几组不同规模的测试数据，这里放一组典型结果（本地环境：某普通台式机，Java）：

数据规模小时，三者速度差异肉眼完全看不出来；但数据规模到十万级以上，哈希表法由于需要维护哈希集合和可能的哈希冲突，实际耗时往往会比双指针法高出不少。这也是面试中为什么更推荐双指针法的原因之一：不只是因为它边界处理更优雅，而是真实场景下它的常数因子更小，空间表现也更稳定。

5. 常见错误、调试心得与面试进阶技巧

5.1 高频报错场景与排查方法

第一个高频报错是空指针异常。常见位置是pA.next或pB.next，因为指针已经为 null 还在访问它的属性。双指针法里尤其要注意：pA = (pA == null) ? headB : pA.next，这里先用三目运算符判断是否为空，再决定是否访问next属性，顺序不能反。如果写成pA = pA.next == null ? headB : pA.next，当 pA 为 null 时就直接解引用了。

第二个高频报错是死循环。这多半是在手工模拟双指针时，没有把"指针走完链表后切换表头"这个动作写对，导致两个指针永远在同一段链表里原地打转。还有一个可能原因是链表构造出了问题：两个链表的尾节点没有置为 null，形成循环链表，这种情况下任何解法都会陷入无限循环。

第三个问题是结果输出不符合预期。我遇到过很多次，自己构造测试用例时，两个链表的值都正确，交点也设置了，但程序返回 null。后来排查发现，我构造链表时传递的公共节点和链表 B 里接的那个节点不是同一个对象，而是两个值相同的独立节点。这种问题非常隐蔽，排查时一定要检查构造链表的代码，而不是急着怀疑算法。

5.2 构造自测用例的三个关键技巧

构造用例时，建议先把"无交点"的情况测一遍，再测"有交点但一个链表很长"的情况，最后测"交点就在第一个节点"的情况。这个顺序能覆盖最长路径、最短路径和极端初始节点，基本可以保证代码不出低级问题。

还有一个技巧是：手动模拟一遍双指针的走动过程。我习惯把 pA 和 pB 的位置变化画在草稿纸上，每走一步记录一次。比如 A 链表长度为 5，B 链表长度为 6，公共段长度为 2。随着指针一步步走，你会发现 pA 在遍历完 A 的 5 个节点后切到 B 的头部，再走 4 个节点到达交点；pB 在遍历完 B 的 6 个节点后切到 A 的头部，再走 3 个节点到达交点。虽然两者走过的链表段不同，但最终同时到达同一个交点，这种模拟会让你对算法的正确性产生真正的信任感。

5.3 面试时如何一步步引导出双指针解法

如果在面试中遇到这道题，建议的回答节奏是：先给出哈希表方案，说明"我可以先遍历链表 A 存入哈希表，再遍历链表 B 查找第一个相同节点"，这样做的时间复杂度 O(m + n)，空间 O(m)。然后主动提出优化方向："这道题要求尽量节省空间，有没有 O(1) 空间的办法？"

接下来抛出长度差法：先统计两个链表的长度，让长链表指针先走差值步，再同步遍历，找第一个相同节点。这个方案面试官通常能听懂，但你还可以更进一步："还可以用双指针法，让两个指针分别遍历 A+B 和 B+A，总长度一致后自然同时到达交点。"这样一步步递进，展现出的是主动优化和思路演进的过程，而不是死背答案。

5.4 从相交链表延伸出的三个变种题

这道题学透之后，可以顺带练习几个变种。第一个变种是"如何判断两个链表是否相交"，不要求返回交点，只返回布尔值。其实只要双指针跑一遍，最后看 pA 和 pB 是否同时为 null 即可，代码几乎一样。

第二个变种是"如果链表可能有环，怎么找相交节点"。问题会复杂一些，需要先用快慢指针判断链表是否有环，找到环入口后，再结合哈希表或者其他方式处理。这个变种在高级面试里偶尔出现，可以提前研究一下。

第三个变种是"在只给定两个链表中某个节点的情况下，如何判断这个节点是否属于某个链表"。这本质上是"能否从给定节点走到链尾"的问题，不用整条链表操作，但能考察对链表尾部和 null 的理解。把 160 题的三种解法彻底弄明白后，这些变种都会变得容易很多。

6. 我的一些实操体会

这道题我前前后后大概刷过四五遍，每次重刷都有新的体会。第一次是刚学链表时，只能写出暴力嵌套循环，提交后被超时教育了；第二次学了哈希表，能通过但心里不踏实；第三次彻底搞懂双指针之后，才发现以前纠结的"指针切换顺序"其实只是表象，真正关键的是"两个指针走的总路程相同"。这个认知一旦建立，后续碰到类似的"寻找共同终点"类题目，都会条件反射地想到双指针思路。

如果你正在准备面试，我的建议是：不要只背双指针的代码。你可以在白纸上把链表 A 和 B 画出来，模拟一遍指针移动的完整过程，尤其是交点偏前、交点偏后、完全不相交这三种情况，都走一遍。花二十分钟做这件事，比你背二十遍代码都有用。

最后分享一个逃不掉的小经验：实际写代码时，一定把判空放在最前面。不管你想写多优雅的解法，如果 headA 或 headB 为空，直接返回 null 是最稳妥的。这个习惯能让你在那种指针移动复杂的环境里省下大量调试时间。