面试链表题十有八九逃不开 LeetCode Hot 热题100 里的第160题“相交链表”。难度标着 easy但我见过不少第一次做这题的人在本子上画了半小时指针最后还是掉了坑。这题表面上是判断两个单链表有没有交点、把交点找出来但背后藏着两个经典套路哈希集合和双指针。尤其双指针那套“互相换路”的思路是面试里极其加分的亮点。这篇文章我会把这道题从头到尾过一遍——怎么读题、怎么搭思路、怎么写代码、怎么补测试包括一些我实际踩过的边界坑适合准备大厂算法面试的开发者也适合刚用链表练手的新人。1. 先搞懂题目到底在问什么1.1 相交不是比“值”是比“引用”先明确一个关键概念两个链表相交指的是两个链表在某个节点开始后续节点完全相同也就是说它们共享同一段内存引用。注意这里不是比节点里的 val 是否相等而是看节点的引用地址是否一致。举个典型例子A: a1 - a2 ----------------c1 - c2 - c3 \ / B: b1 - b2 - b3 -------从 c1 开始A 和 B 后面的节点完全共用。题目要求返回 c1 这个节点。如果两个链表没有共享的后续节点返回 null。很多刚开始刷题的人容易把“节点值相等”和“节点相交”混为一谈这是这道题的第一道坑。比如两个链表恰好某个位置的值都是 5但它们在内存里是两码事这种不能算相交。面试官如果看到你把相同值的节点当成交点基本就觉得你对链表的结构不理解。1.2 既然是 easy为什么还有人卡住题目难度虽然是 easy但它不像“反转链表”那样直接给出操作步骤。这里难在没有立刻能想到的迭代方式因为输入是两个独立的链表头你无法预知它们各自多长也不知道交点在哪里。最容易想到的暴力做法是遍历链表 A 的每个节点对每个节点再遍历链表 B看有没有相同的引用。这种做法的复杂度是 O(m*n)m 和 n 分别是两个链表的长度。在数据量大一点的时候跑起来非常吃力面试中这种写法基本不会让人满意。所以这道题真正的考点不是“你会不会遍历”而是能不能把两个链表的路径关系想明白然后用更聪明的方式让两个指针在未知长度的情况下对齐。1.3 动手之前先建立三个直觉在写代码之前我通常会先给新人讲清三个关于链表的基本事实它们是解这道题的地基单向链表的每个节点只有一个 next 指针所以一旦两个链表相交相交之后的所有节点必然完全重合整体形状像个 Y而不是 X。因为每个节点只有一条 next所以交点不可能出现“相交之后又分开”的情况。两个链表的长度差只存在于相交点之前的部分公共部分的长度对两个链表来说是一样的。把这三个事实记住再看那些花哨的解法就一点都不玄了。2. 三种解法拆解从暴力到最优2.1 哈希集合法最直接、最好想的做法第一种解法思路非常直白遍历链表 A把每个节点的引用存进一个哈希集合HashSet然后再遍历链表 B检查每个节点是否已经存在于集合中第一个存在的就是交点如果遍历完整条 B 都没有说明不相交。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { SetListNode visited new HashSet(); ListNode p headA; while (p ! null) { visited.add(p); p p.next; } p headB; while (p ! null) { if (visited.contains(p)) { return p; } p p.next; } return null; }为什么用 HashSet 而不是 ArrayList因为 HashSet 的 contains 操作是 O(1) 级别的而 ArrayList 的 contains 是 O(n)。如果用 ArrayList整体复杂度会退化回 O(m*n)跟暴力没区别。这种解法的时间复杂度是 O(mn)空间复杂度是 O(m)。它适合作为面试中的“保底方案”能很快写出来但面试官大概率会追问一句“能不能把空间复杂度优化到 O(1)”2.2 双指针法面试官最想看到的答案双指针法是这道题最经典的解法也是我推荐你优先掌握的。先看完整代码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; }这段代码非常短但每次让新人解释“为什么这么写能相遇”很多人就卡住了。我来拆解一下它的核心逻辑。用两个指针 pA 和 pB 分别从 headA 和 headB 出发同步前进。当 pA 走到链表 A 的末尾时让它跳到链表 B 的头节点继续走当 pB 走到链表 B 的末尾时让它跳到链表 A 的头节点继续走。这样做的结果是两个指针最终会在“同一个位置”相遇。为什么一定会相遇假设链表 A 独立部分的长度为 a链表 B 独立部分的长度为 b公共部分的长度为 c。pA 实际走过的距离是a c b也就是先把 A 完整走完再去走 B 的独立部分。pB 实际走过的距离是b c a也就是先把 B 完整走完再去走 A 的独立部分。这两个距离是相等的。当两个指针走过的总路程相等而它们的步长都是 1所以它们会在同一时刻到达同一个节点。如果链表有交点这个节点就是交点如果链表没有交点它们会在各自走完 ab 的路程后同时变成 null此时 pA pB 为 true循环结束返回 null。如果这里觉得抽象可以想象两个人分别走两条路但两条路最终会汇合成一条大路。他们各自从不同的起点出发如果让每个人都走“自己的路 对方的路”走的总路程是一样的最终必然在大路上碰头。2.3 对齐长度法最容易理解的非暴力解除了双指针还有另一种思路也很好理解先把两个链表的长度计算出来让较长的链表指针先走掉长度差的那几步然后两个指针再同步前进。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA getLength(headA); int lenB getLength(headB); ListNode pA headA; ListNode pB headB; if (lenA lenB) { int diff lenA - lenB; while (diff-- 0) pA pA.next; } else { int diff lenB - lenA; while (diff-- 0) pB pB.next; } 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; }这种做法的核心是消除长度差。两个链表相交之后的部分是相同的如果让指针在“剩余路程相同”的前提下起步两个指针逐个节点走必然同时走到交点。我个人的看法是如果你想在面试中把思路讲得清楚、让面试官快速跟上长度对齐法是很好的选择。它的缺点是代码比双指针长一些需要额外的长度计算而且需要遍历两次链表。但面试时写出这个解法也完全没问题属于高效且易懂的方案。2.4 复杂度与适用场景对比解法时间复杂度空间复杂度实现难度适用场景暴力双重遍历O(m×n)O(1)最简单仅用于理解题意哈希集合法O(mn)O(m)简单追求快速写出的保底方案双指针法O(mn)O(1)中等面试推荐答案长度对齐法O(mn)O(1)简单思路清晰适合现场讲解从面试视角看双指针法是性价比最高的答案——代码足够短空间占用足够小还能展示你对“路程相等”这个数学本质的理解。长度对齐法则更适合你自己在平时练习时用来加深理解。3. 代码实现与核心细节解析3.1 Java 双指针解法详析上面已经给出双指针的完整 Java 实现这里补充一个非常关键的细节pA (pA null) ? headB : pA.next;这行代码很多人一开始会写错有的写成pA (pA.next null) ? headB : pA.next;这会导致链表在到达最后一个节点时不会触发“换路”操作而是直接跳到 headB看起来好像也能跑对但实际少走了一个节点。因为“换路”的时机应该是在 pA 已经变成 null 之后也就是完整走完整个链表 A 之后而不是在最后一个节点就提前换。还有一个容易忽略的地方当两个链表没有交点时最终 pA 和 pB 会同时变成 null。循环的退出条件是 pA ! pB遇到 null null 的情况条件为 false循环正常结束。这个过程不需要额外处理非常优雅。我建议初学者在 IDE 里单步调试一遍双指针代码观察指针值的变化。看到 pA 走到 null 再切换到 headB 的那一刻你才能真正理解这段代码的精妙。3.2 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 pA这里一个常见的疑问是pA pA.next if pA else headB在 pA 为 null 时设置成 headB会不会导致无限循环不会。因为当两个链表不相交时pA 和 pB 分别走完 lenA lenB 的路程后会同时变成 null循环就结束了。如果相交它们会在进入公共部分后相遇循环也会结束。关键在于两个指针走的“总路程”完全相等所以无论如何循环都会在有限步内退出。3.3 指针“换路”的现场走位演示为了帮助你把指针的移动过程刻在脑子里我做一个具体的走位演示。假设链表如下A: a1 - a2 - c1 - c2 - c3 B: b1 - b2 - b3 - c1 - c2 - c3pA 初始在 a1pB 初始在 b1。pA 依次经过 a2、c1、c2、c3然后变成 null再跳到 b1。pB 依次经过 b2、b3、c1、c2、c3然后变成 null再跳到 a1。之后 pA 继续走 b2、b3、c1pB 继续走 a2、c1。最终两个指针在 c1 相遇。这个过程本质上是让 pA 走“A 全段 B 的交点前段”pB 走“B 全段 A 的交点前段”总路程相同于是同时抵达交点。3.4 边界条件大汇总链表题最怕边界条件这里把 160 题会遇到的情况全部列出来两个链表都为空直接返回 null。双指针写法里会先做空值判断防止 NPE。其中一个链表为空同样返回 null。两个链表完全相同headA 和 headB 指向同一个头节点第一轮 while 判断 pA ! pB 直接为 false返回头节点。交点位于第一个节点之后的部分正常流程双指针会相遇。没有交点pA 和 pB 在走完总路程后同时为 null返回 null。写代码时不管用哪种解法都应先处理空链表的情况。这个习惯能帮你省掉很多测试阶段的无谓报错。4. 单元测试把算法写得可靠4.1 为什么要专门写测试很多人刷算法题只在平台上点“提交”过了就算完。但我觉得在本地写几个测试用例跑一遍价值非常大。因为平台只会告诉你最终的对错不会告诉你到底哪一步错了。自己设计测试用例能够验证对边界条件的理解也能在面试手写代码后快速自查。4.2 测试用例设计思路针对“相交链表”这道题我一般会设计下面几类场景两个链表正常相交于中间节点覆盖主流程。两个链表不相交覆盖返回 null 的分支。其中一个链表为空覆盖空值处理。两个链表完全相同覆盖“第一个节点就是交点”的情况。两个链表长度差距很大但相交于很靠后的位置覆盖双指针换路的关键逻辑。交点在其中一个链表的头节点比如 B 和 A 完全重合或者 B 的头节点就是 A 的某个中间节点。4.3 测试代码实现在本地写测试时可以用一个简单的 main 方法配合自定义辅助函数来构造链表。下面是一个 Java 示例public class IntersectionTest { // 生成一个带头节点的链表 private static ListNode createList(int[] values) { ListNode dummy new ListNode(-1); ListNode cur dummy; for (int v : values) { cur.next new ListNode(v); cur cur.next; } return dummy.next; } // 找到链表中的第 index 个节点从 0 开始 private static ListNode getNode(ListNode head, int index) { ListNode cur head; while (index-- 0) { cur cur.next; } return cur; } public static void main(String[] args) { // 用例1正常相交 int[] aVals {1, 2, 3, 4, 5}; int[] bVals {9, 8}; ListNode common createList(new int[]{7, 8, 9}); ListNode headA createList(aVals); ListNode headB createList(bVals); ListNode tailA getNode(headA, 4); ListNode tailB getNode(headB, 1); tailA.next common; tailB.next common; Solution solution new Solution(); ListNode result solution.getIntersectionNode(headA, headB); System.out.println(用例1结果: (result null ? null : result.val)); // 用例2不相交 ListNode headA2 createList(new int[]{1, 2, 3}); ListNode headB2 createList(new int[]{4, 5}); result solution.getIntersectionNode(headA2, headB2); System.out.println(用例2结果: (result null ? null : result.val)); } }这里有个我实际踩过的坑构造链表时如果直接用“新建节点”的方式来拼接公共部分比如先 createList 得到公共链表然后又用 createList 构造 A再把 A 的尾部指向公共链表这种方式是正确的。但如果试图用 createList 再构造一串值相同的节点来“模拟”相交那段新链表和原链表根本不会共享引用测试结果永远是 null。测试代码里必须确保公共部分是同一批节点对象。4.4 测试运行结果分析实际跑下来正常相交的用例会打印出公共部分第一个节点的值比如 7不相交的用例打印 null。如果你用断言框架比如 JUnit还可以把期望值写进断言这样每次改动代码后重跑测试能第一时间发现回归问题。写测试的一大好处是你可以放心地重构解法。比如从哈希集合法改成双指针法改完直接跑一遍所有用例全绿就说明你的改动没有破坏核心逻辑。5. 避坑指南与面试经验5.1 双指针法常见的三个坑第一个坑是换路时机写错。前面已经强调过必须在 pA 等于 null 时才换到 headB不能提前也不能延后。延后会导致指针走到 null 之后还尝试访问 next直接抛空指针异常。第二个坑是忘记处理空链表。如果 headA 或 headB 为 null直接进入 while 循环会在 pA 或 pB 为 null 时立刻跳出返回的是 null结果没错但一些语言的写法会把pA.next放在前面这就炸了。第三个坑是没有想清楚循环终止条件。很多人担心两个指针不会相遇陷入死循环。实际上只要 pA 和 pB 每次都移动一步并且都遵循“走到尾换另一条链表”的规则两个指针总会在最多 mn 步后相遇或同时为 null。这个结论可以用穷举法验证也可以从“路程相等”的数学推导中得到。5.2 如果链表有环该怎么办LeetCode 这道题默认链表是无环的但面试官很可能追加扩展问题如果有环呢这个情况会比较复杂因为交点可能出现在环上。基本思路是先用快慢指针判断链表是否有环再定位环的入口最后在两个链表的无环部分做常规操作。这个问题本身可以单独写一篇长文面试中能主动提一句“这题假设无环但如果限定存在环需要额外处理”会让面试官看到你在边界思考上的严谨。5.3 面试答题的节奏建议我个人的经验是拿到这道题不要直接写代码。先跟面试官确认几个信息链表是否有环没有是简单版本如果没有交点返回什么null是否允许修改链表结构不允许确认完毕后先讲哈希集合法作为“第一直觉”然后主动说“但空间复杂度不够好能不能优化到 O(1)”——这样自然引出双指针。讲双指针时重点讲清“两个指针走的总路程相同”这一核心而不是背代码。最后动手写代码之前简要说明你会怎么处理空链表和不相交情况。这样的节奏会显得你思路清晰、表达有条理比闷头写代码然后等测试结果要有利得多。5.4 常见误区速查表误区正确理解节点值相同就是交点必须判断引用地址相同相交链表可能呈 X 型单向链表相交后只能完全重合呈 Y 型双指针会死循环总路程相等最多走 mn 步即终止换路时机在最后一个节点必须在走到 null 后再换路不需要处理空链表必须先判空否则可能空指针异常只用哈希集合法就够了能通过但空间非最优面试建议展示双指针这几年我带过不少新人发现这道题最容易让人困惑的点反而是它太短了——核心解法就这么几行所以很多人直接背答案没弄懂背后“路程相等”的思想。一旦理解了双指针为什么能相遇再做 LeetCode 上其他链表类题目比如环形链表、合并有序链表都会顺手很多。这种“一条路走不完就换一条路接着走”的思维其实跟很多业务系统里的重试机制、容错切换也很相通。刷题之余能琢磨到这一层算法才算真正学活。