从Hot 100的第18题开始终于轮到链表题了。160. 相交链表算是链表题型里非常经典的一道题目本身难度不高但背后藏的考点一点都不少指针操作、引用比较、空间复杂度优化、还有面试时经常被追问的为什么双指针一定会相遇。我用了一下午把整道题的思路、证明、代码和坑都重新过了一遍今天把它们全部写下来给正在刷Hot 100的朋友做个参考。1. 先弄明白这道题到底在考什么1.1 题目回顾与核心信号题目描述很直白给两个单链表的头节点 headA 和 headB请找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null。注意题目有个很重要的约束函数返回结果后两个链表必须保持原来的结构。也就是说你不能通过把某个节点的 next 改来改去来标记访问过的位置所有操作只能靠额外变量或者循环本身完成。从高频考点角度拆一下这道题至少覆盖了三个能力点第一链表的遍历和指针操作是否熟练第二能否理解引用相等和值相等的区别第三能不能在面试官的步步追问下从 O(mn) 的暴力解一路优化到 O(1) 额外空间的最优解。LeetCode 把这道题放进 Hot 100不是因为它难而是因为它非常适合考察综合的代码功底。1.2 看懂相交的定义避开90%的人都会踩的坑相交这个词是整道题最容易理解错的地方。两个链表相交指的是从某个节点开始后面所有的节点在内存中是同一个对象而不是两个节点的值恰好相同。举个例子链表 A 是 4 - 1 - 8 - 4 - 5链表 B 是 5 - 6 - 1 - 8 - 4 - 5。从值上看B 里的第二个节点也是 1A 里的第二个节点也是 1但它们是两个完全不同的节点对象只是数字碰巧一样。真正相交的地方是值同为 8 的那个节点从它之后A 和 B 共享同一段节点。所以判断两个节点是否相同必须用引用相等来判断。Java 里两个对象用 比较的就是引用地址Python 里用 is 判断身份这和在数组中比较两个数字是否相等完全是两码事。我第一次刷这题的时候就是下意识写了 pA.val pB.val结果自测用例跑出来发现到了1那个节点就返回了显然不对。这个坑必须一开始就意识到。2. 解法一暴力双循环为什么不能靠它杀死比赛2.1 思路与代码暴力法的思路没有任何技巧拿着链表 A 的每一个节点去链表 B 里从头到尾遍历一遍如果发现 A 的当前节点和 B 的某个节点是同一个引用就说明找到了交点。Python 代码如下class Solution: def getIntersectionNode(self, headA, headB): pA headA while pA: pB headB while pB: if pA is pB: return pA pB pB.next pA pA.next return None这段代码逻辑极简一个外层循环套一个内层循环没有任何状态需要维护。它一定能得到正确答案不涉及任何花哨的技巧用来作为思考起点是合格的。2.2 复杂度分析O(mn) 到底多离谱假设链表 A 的长度为 m链表 B 的长度为 n。外层每选出一个 A 的节点内层就要把 B 完整扫一遍所以总比较次数是 m 乘以 n时间复杂度 O(mn)。当 m 和 n 都接近 10 万时理论比较次数是 100 亿次即便每次比较只需要几纳秒也是分钟级别甚至更久的耗时这在刷题和面试里都是不可接受的。额外空间倒是 O(1)因为只用了两个指针变量。这算是暴力法唯一的优点但在时间复杂度的灾难面前这个优点基本没有竞争力。很多新手觉得暴力法反正能过一部分测试点但 LeetCode 的用例设计得很全面最后几个大数据量用例几乎必然超时。所以这道题如果第一反应是双循环那么面试官心里已经开始等你给出优化方案了。2.3 面试沟通技巧暴力解的正确打开方式说句实在话暴力解并不是毫无价值它的价值在于帮你快速确认题意也给了自己一个思考缓冲。我在面试中遇到这类链表题通常先花 30 秒把暴力思路说出来然后立刻补一句这个解法时间复杂度是 O(mn)明显不够好我们能不能用哈希或者双指针把时间复杂度降到 O(mn)。这样面试官会认为你具备复杂度意识而不是只会背题。真正需要注意的是千万别在暴力解上面耗太久更别直接上手写完整代码。先把暴力思路用几句话交代清楚然后主动进入更优解法的讨论这是面试里最稳妥的节奏。3. 解法二哈希集合能用但说不出道理就是白搭3.1 思路与代码哈希表的思路也很直观先遍历链表 A把每个节点的引用存进一个 HashSet再遍历链表 B每走到一个节点就检查它是否已经在集合里。如果存在说明这个节点是 A 和 B 的公共节点也就是交点。public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { SetListNode seen new HashSet(); ListNode cur headA; while (cur ! null) { seen.add(cur); cur cur.next; } cur headB; while (cur ! null) { if (seen.contains(cur)) { return cur; } cur cur.next; } return null; } }这段 Java 代码是哈希解法最常见的形态。先用一个 while 循环把 A 的节点全部入集合再用第二个 while 循环遍历 B 并检查命中。因为 HashSet 的 add 和 contains 平均时间复杂度都是 O(1)所以整体耗时是线性的。3.2 空间复杂度是硬伤但并非一无是处这个解法的时间复杂度是 O(mn)已经够优秀了。问题出在空间上额外使用了一个最大能装下 m 个节点的哈希集合所以空间复杂度是 O(m)。面试官看到这个解法几乎一定会追问能不能把空间复杂度也优化到 O(1)如果你能立刻答出双指针法这一轮就很加分如果答不上来前面哈希解法的印象分就保不住了。另外有一个非常容易忽略的细节哈希集合里存的是节点引用不是节点的值。之所以强调这一点是因为如果把 int 类型的 val 存进集合那么在遍历 B 时遇到值相同但不是交点的节点就会误判结果就是错。这也是为什么哈希解法特别适合用来给面试官展示你对引用相等的理解。你可以在代码注释里写一句这里 HashSet 的元素是 ListNode 对象本身val 相同的不同节点并不会被判定为相等。4. 解法三双指针法这道题最优雅的答案4.1 核心思路把两条链表拼接起来双指针法是被公认的最优解时间和空间都压到了极限。思路用一句话概括两个指针分别从 A 和 B 的头节点出发各自走到末尾变成 null 之后换到另一条链表的头节点继续走直到两个指针指向同一个节点或者同时走到 null。为什么换着走就能相遇想象把链表 A 和链表 B 拼接成两条虚拟的长链表虚拟链表一的顺序是A 的全部节点 B 的全部节点虚拟链表二的顺序是B 的全部节点 A 的全部节点这两条虚拟链表的长度都是 mn完全相等。指针 pA 在虚拟链表一上从头走到尾指针 pB 在虚拟链表二上从头走到尾。因为速度相同、总路程相同它们最终会同步到达终点。如果 A 和 B 存在交点那么在某个时刻两个指针会同时站在同一个节点上如果不存在交点它们最终会同时走到 null循环终止返回 null。4.2 为什么双指针一定会在交点相遇路程证明这一部分是整个题解的核心面试时被追问概率极高建议每个刷题的人都把这个证明吃透。假设链表 A 的非公共部分长度为 a链表 B 的非公共部分长度为 b两条链表的公共部分长度为 c。如果存在交点那么pA 的完整轨迹从 A 头出发走完 A 的全部 ac 个节点到 null然后从 B 头进入再走 b 步到达交点总步数 acbpB 的完整轨迹从 B 头出发走完 B 的全部 bc 个节点到 null然后从 A 头进入再走 a 步到达交点总步数 bcaacb 和 bca 是同一个表达式必然相等。而两个指针每一步移动一个节点速度完全相同所以它们走了相同步数之后一定会同时出现在交点。如果两个链表不相交此时 c0。pA 走完 A 需要 a 步再走完 B 需要 b 步总步数 abpB 走完 B 需要 b 步再走完 A 需要 a 步总步数也是 ab。它们在走完各自全程的那一刻同时到达 null循环退出返回 null。整个过程不需要额外的哈希表也不需要统计链表长度逻辑干净利落。这也是为什么这个解法被很多面试官当作链表综合能力的最佳考题。4.3 多语言实现Java / Python / GoJava 实现public class Solution { 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; } }Python 实现class Solution: def getIntersectionNode(self, headA, headB): if not headA or not headB: return None pA, pB headA, headB while pA is not pB: pA headB if pA is None else pA.next pB headA if pB is None else pB.next return pAGo 实现func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA nil || headB nil { return nil } pA, pB : headA, headB for pA ! pB { if pA nil { pA headB } else { pA pA.Next } if pB nil { pB headA } else { pB pB.Next } } return pA }三种语言的实现思路完全一致区别只在于引用比较的语法。Java 用 Python 用 isGo 用 本质上都是比较指针本身。这里有一个容易写错的细节pA 在走向 null 之后要立刻切到另一条链表的头部而不是等 pA 变成 null 后再手动赋值。用三元表达式写最容易保持逻辑清晰但要确保判断是 pA null 而不是 pA.next null否则会漏掉走到末尾的那一步切换。5. 边界条件、自测用例与实战排坑5.1 空链表与不相交情况的处理很多解法第一行就判断 headA 或者 headB 是否为空这其实是防御性编程的习惯。如果其中一个链表为空那么它们不可能有交点直接返回 null 是最合理的。即便不判断双指针法也会因为 pA 和 pB 都为 null 而退出循环并返回 null但提前判断能让代码意图更明确。不相交的情况在双指针法里已经被自然处理了两个指针同时走完两条链表最终同时指向 null循环条件 pA ! pB 不成立退出循环返回 pA 也就是 null。这里没有死循环风险因为两个指针的总步数完全相同。5.2 自测用例设计思路我建议刷链表题时不要只盯着题目给的示例最好自己设计几组边界用例。对于相交链表我一般至少测这五组场景输入示意预期结果正常相交A: 4-1-8-4-5B: 5-6-1-8-4-5返回值为 8 的节点不相交A: 1-2-3B: 4-5null一个为空A: nullB: 1-2null头节点就相交A 和 B 完全指向同一链表返回头节点仅末尾节点相交A: 1-2-3B: 4-2-3 且 2、3 是共享节点返回值为 2 的节点这里尤其要注意头节点就相交的情况很多人的代码在此时会直接返回 headA因为还没有进入循环前 pA 和 pB 已经相等。实测下来双指针法和哈希法对这种情况都能正确处理但暴力法在头节点相交时也能直接命中反而是最直观的。5.3 这个坑我踩过值相等不等于节点相等之前提到过这道题最容易踩的坑就是把节点的值相等当成节点相等。我在实际刷题时专门写过一版错误的比较方式if pA.val pB.val: return pA这个写法在最开始的示例用例里可能碰巧是对的因为示例中确实只有一个地方值相同。但一旦遇到 B 里也有一个值为 1 的节点程序就会在错误的位置提前返回。更准确地说链表中的相同值是完全合法的两个不同节点上完全可以存放相同的数字。判断相交必须基于内存地址也就是对象身份。还有一个很容易被忽略的点如果题目没有说明整个链式结构中不存在环那么你还得先考虑链表有环怎么处理。LeetCode 160 的题目描述里已经保证了无环所以常规解法不需要考虑环的问题。但面试时如果面试官临时改动前提你就要能接住这个追问。6. 面试官会怎么追问以及这道题的周边6.1 追问链从 O(mn) 到 O(1) 的完整演进一个典型的面试片段是这样的面试官请找出两个链表的交点。 你用暴力双循环O(mn)。 面试官能优化吗 你用哈希集合O(mn) 时间O(m) 空间。 面试官空间能省掉吗 你用双指针O(mn) 时间O(1) 空间。 面试官证明一下双指针为什么是对的。把这条追问链走通你就把这道题的核心价值全部展示完了。所以刷题的时候不要满足于Accepted而是要把每一步的复杂度变化和正确性证明都想明白。6.2 进阶如果链表可能有环怎么办这是我在社区里看到的高频追问方向。如果两个链表中存在环比较麻烦因为长度不再适用于简单拼接法而且双指针的终止条件也需要重新设计。不过在产品面试里这个追问更多的是考察你的思维灵活性。你可以先说明带环场景下的复杂性然后提出一种思路先用快慢指针判断两个链表是否有环再分别找到环的入口最后比较环入口是否相同。虽然实现步骤变多但这说明你能把环形链表相关的解法迁移过来。6.3 相关题目地图与刷题建议题目核心考点与 160 的关联141. 环形链表快慢指针判断是否有环双指针思想的延伸142. 环形链表 II快慢指针找环入口同样是双指针相遇问题证明方式类似876. 链表的中间结点快慢指针找中点双指针的前置基础19. 删除链表的倒数第 N 个结点双指针制造距离差双指针的另一种用法160. 相交链表双指针拼接两链本次刷题主角我在刷完 160 后会顺手把 141、142 再过一遍因为这四道题组成了一条完整的双指针链表题训练链。与其零散地刷不如集中几天内连续刷完效果会好很多。7. 写在最后这道题给我留下的三点体会第一一定要把节点相等和值相等刻在脑子里。这道题让我养成了一个习惯凡是链表、树、图这类由对象组成的结构只要判断是否同一个节点一律问自己一句这里该用引用比较还是值比较第二双指针法的证明远比代码本身重要。很多人能默写出代码但被问到为什么两个指针最终会相遇时支支吾吾。我后来在面试前会把这种常用证明用一两句话重新推一遍确保自己能讲清楚总路程相同速度相同所以同时到达这个逻辑链条。第三刷题要有意识地串成专题。160 只是 Hot 100 系列里的第 18 题但它背后的双指针技巧可以辐射到环形链表、删除倒数第 N 个节点等一系列题目。每一道题都不该是孤立的记忆点而应该是整个知识网络里的一个连接点。最后说个我自己常用的做法每刷完一道题我会把三种解法写在同一个文档里标注各自的复杂度再用一句话概括每种解法的适用场景。等 Hot 100 刷完这份文档就是最好的面试复习资料比临时翻题解高效得多。