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) { SetListNode 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 后切到 headBpB 走到 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方案链表长度组合耗时纳秒级空间占用哈希表法m10000n8000约 3 毫秒依赖哈希表大小双指针法m10000n8000约 1 毫秒O(1)长度差法m10000n8000约 1.2 毫秒O(1)数据规模小时三者速度差异肉眼完全看不出来但数据规模到十万级以上哈希表法由于需要维护哈希集合和可能的哈希冲突实际耗时往往会比双指针法高出不少。这也是面试中为什么更推荐双指针法的原因之一不只是因为它边界处理更优雅而是真实场景下它的常数因子更小空间表现也更稳定。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 链表长度为 5B 链表长度为 6公共段长度为 2。随着指针一步步走你会发现 pA 在遍历完 A 的 5 个节点后切到 B 的头部再走 4 个节点到达交点pB 在遍历完 B 的 6 个节点后切到 A 的头部再走 3 个节点到达交点。虽然两者走过的链表段不同但最终同时到达同一个交点这种模拟会让你对算法的正确性产生真正的信任感。5.3 面试时如何一步步引导出双指针解法如果在面试中遇到这道题建议的回答节奏是先给出哈希表方案说明我可以先遍历链表 A 存入哈希表再遍历链表 B 查找第一个相同节点这样做的时间复杂度 O(m n)空间 O(m)。然后主动提出优化方向这道题要求尽量节省空间有没有 O(1) 空间的办法接下来抛出长度差法先统计两个链表的长度让长链表指针先走差值步再同步遍历找第一个相同节点。这个方案面试官通常能听懂但你还可以更进一步还可以用双指针法让两个指针分别遍历 AB 和 BA总长度一致后自然同时到达交点。这样一步步递进展现出的是主动优化和思路演进的过程而不是死背答案。5.4 从相交链表延伸出的三个变种题这道题学透之后可以顺带练习几个变种。第一个变种是如何判断两个链表是否相交不要求返回交点只返回布尔值。其实只要双指针跑一遍最后看 pA 和 pB 是否同时为 null 即可代码几乎一样。第二个变种是如果链表可能有环怎么找相交节点。问题会复杂一些需要先用快慢指针判断链表是否有环找到环入口后再结合哈希表或者其他方式处理。这个变种在高级面试里偶尔出现可以提前研究一下。第三个变种是在只给定两个链表中某个节点的情况下如何判断这个节点是否属于某个链表。这本质上是能否从给定节点走到链尾的问题不用整条链表操作但能考察对链表尾部和 null 的理解。把 160 题的三种解法彻底弄明白后这些变种都会变得容易很多。6. 我的一些实操体会这道题我前前后后大概刷过四五遍每次重刷都有新的体会。第一次是刚学链表时只能写出暴力嵌套循环提交后被超时教育了第二次学了哈希表能通过但心里不踏实第三次彻底搞懂双指针之后才发现以前纠结的指针切换顺序其实只是表象真正关键的是两个指针走的总路程相同。这个认知一旦建立后续碰到类似的寻找共同终点类题目都会条件反射地想到双指针思路。如果你正在准备面试我的建议是不要只背双指针的代码。你可以在白纸上把链表 A 和 B 画出来模拟一遍指针移动的完整过程尤其是交点偏前、交点偏后、完全不相交这三种情况都走一遍。花二十分钟做这件事比你背二十遍代码都有用。最后分享一个逃不掉的小经验实际写代码时一定把判空放在最前面。不管你想写多优雅的解法如果 headA 或 headB 为空直接返回 null 是最稳妥的。这个习惯能让你在那种指针移动复杂的环境里省下大量调试时间。