刷到 Hot100 第 18 题160. 相交链表。说实话这道题在链表专题里属于“看起来简单、做起来容易绕”的典型代表。我最早在面试里遇到这题时第一反应是两层循环暴力判断被面试官追问了一句“能不能 O(1) 空间”之后整个人就开始慌了。后来自己把两种主流解法、数学原理和边界条件都梳理了一遍才觉得这题是真的值得好好写一篇复盘。这篇文章适合正在刷 LeetCode Hot100 的读者也适合准备面试想系统过一遍链表题的人。我会把题意、哈希表方案、双指针方案、长度对齐法、常见踩坑点以及延伸变体一次讲透争取让不同基础的读者都能跟着完整的思路把这道题彻底拿下。1. 题目到底在问什么1.1 什么是真正的“相交”题目给两个单链表的头节点 headA 和 headB要你返回它们相交的第一个节点如果没有相交返回 null。这里的“相交”指的是节点层面的重合不是值相等。两个链表从某个节点开始后面的所有节点都指向同一批节点形成一个大写的 Y 字形结构。比如链表 A 是 A1 - A2 - C1 - C2 - C3链表 B 是 B1 - B2 - B3 - C1 - C2 - C3那么 C1 就是我们要找的相交节点。为什么一定是 Y 型而不是 X 型因为单链表每个节点只有一个 next 指针。一旦两个链表在某个节点合并它们后面走过的路径就必须完全一致不可能出现先相交、再分开、再相交的情况。X 型结构意味着某个节点有两个 next这在单链表里不成立。很多第一次写这道题的人会把“值相等”当成“节点相等”结果一跑测试用例就出问题。LeetCode 里的链表节点值是可以重复的比如 A 链表里有节点值 3B 链表里也有节点值 3但它们是两个不同的节点对象只是恰好值相同。判断相交必须比较节点本身在 Java/C 里比较对象引用在 Python 里比较对象身份而不是比较 val。1.2 题目里容易被忽略的两个约束第一题目明确说给定的两个链表不会构成环。这个约束很重要它保证了很多“走到头再从另一条链表开头继续走”的思路是安全的。如果链表可能带环情况会复杂很多后面我在延伸部分会专门聊。第二函数需要保持原始链表结构不变也就是不能在解题过程中修改节点的 next 指针。这个约束排除了“把 A 的尾巴接到 B 上再找环”这种取巧做法老老实实用路径遍历或者数学技巧去做。2. 暴力方案哈希表法及其价值2.1 思路与实现最直觉的做法是先把链表 A 的所有节点放进哈希集合然后遍历链表 B每到一个节点就检查这个节点是否已经在集合里。如果存在说明这个节点就是交点如果遍历完 B 都没有命中说明两个链表不相交返回 null。这个方案的时间复杂度是 O(mn)空间复杂度是 O(m)其中 m 是链表 A 的长度。代码写起来非常干净public ListNode getIntersectionNode(ListNode headA, ListNode headB) { SetListNode seen new HashSet(); ListNode p headA; while (p ! null) { seen.add(p); p p.next; } p headB; while (p ! null) { if (seen.contains(p)) { return p; } p p.next; } return null; }Python 版本思路一模一样def getIntersectionNode(headA, headB): seen set() p headA while p: seen.add(p) p p.next p headB while p: if p in seen: return p p p.next return None2.2 为什么这个方案仍然值得写哈希表法不是最优解但它是面试里很好的“起点答案”。原因有三个第一正确性一目了然。把 A 的所有节点记下来再在 B 里逐个查逻辑没有任何弯弯绕不容易写错。第二它能作为后面双指针解法的验证基准。我平时刷题如果先写出暴力解会用它跟优化方案的结果对拍确认优化算法没有跑偏。第三面试官听到这个方案后通常会顺着问“空间能不能优化到 O(1)”这就自然地把话头引到了双指针和长度对齐法上。你在面试中先给出能跑的方案再逐步优化这才是正常的思考过程而不是直接背一个双指针答案出来。当然哈希表方案不能作为最终的满意答案因为空间复杂度偏高。链表很长的时候哈希集合会占不少内存。接下来才是这道题真正精彩的部分。3. 双指针解法为什么两个指针一定会相遇3.1 核心思想两个指针 pA、pB 分别从 headA、headB 出发同步往下走。当 pA 走完链表 A就把它重置到 headB当 pB 走完链表 B就把它重置到 headA。继续走直到 pA 和 pB 指向同一个节点。这个节点可能是真正的相交节点也可能是 null两种情况都表示算法结束了。代码极短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 版本def getIntersectionNode(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 pA3.2 数学证明为什么它们会在交点相遇假设链表 A 不相交部分的长度为 a链表 B 不相交部分的长度为 b公共部分的长度为 c。也就是说链表 A 总长是 ac链表 B 总长是 bc。pA 从 headA 出发走完自己的链之后继续走 B 的前半段。当 pA 第一次走到交点时它走过的距离是 a c。随后它会走完公共部分再走完 B 的不相交部分到达 B 的末尾这时候走过的距离是 a c b。pB 从 headB 出发对应的它第一次到达交点时走过的距离是 b c。随后它走完公共部分再走完 A 的不相交部分到达 A 的末尾走过的距离是 b c a。a c b 和 b c a 是相等的。所以在第二轮行走中当 pA 走了 acb 步、pB 走了 bca 步的时候它们都站在同一个位置这个位置刚好就是公共部分的起点也就是交点。如果两个链表不相交可以理解为 c 0。pA 走过的距离是 abpB 走过的距离是 ba最终它们同时走到链表的末尾也就是 null。while 循环的判断条件是 pA ! pB两个指针同时变成 null 时条件不成立循环结束返回 null。这里有个非常微妙的点指针在处理“走完一条链表后换到另一条链表开头”这一动作时不能只做一次。因为长度差可能很大一个指针需要等另一个指针走完它的链表才能进入第二轮。这个“互相抵消长度差”的过程正好是双指针解法的灵魂。3.3 用一个小例子把流程跑通假设链表 A 是 1 - 2 - 3 - 4 - 5链表 B 是 9 - 3 - 4 - 5交点是节点 3。手动模拟一下步数pA 指向pB 指向01912323434545null5null换到 B 的开头 99继续走实际上此时 pB 已走过 9-3-4-5到达 null 后换成 A 的开头 163B 链的节点2A 链的节点7438549null510换成 A 的开头 1null换成 B 的开头 9112312341345145null15nullnull循环结束这个模拟表有点长但它很直观地展示了两个指针是如何通过“换头”操作把长度差抹平的。实际代码里pA 走完 A 后换到 B 的开头pB 走完 B 后换到 A 的开头两者在第二轮后半段会逐渐对齐。3.4 写双指针代码最容易犯的错这里我必须强调一个容易翻车的细节重置指针的操作必须放在 while 循环内部并且在 pA 为 null 时才重置而不是用 if 判断一次就完事。有人会写成这样while (pA ! pB) { if (pA.next null) { pA headB; } else { pA pA.next; } // 同理 pB }这个写法问题很大当一个指针走到最后一个节点时它确实可以换到另一条链表但换过去之后它还需要继续往前走而另一个指针可能还没走完自己的链表。如果你只在“next 为空”时换一次两个指针的第二轮不同步可能导致永远遇不到。正确做法是每走一步都判断当前节点是否为 null如果是 null 就换成另一条链表的头否则继续走 next。这样两个指针每轮都恰好走一步不会因为换链而额外付出步数。4. 长度对齐法另一种必修思路4.1 思路与代码比双指针更容易向别人解释清楚的方法是长度对齐法。先遍历 A 和 B分别求出长度 lenA 和 lenB。假设 A 更长就让 pA 先走 lenA - lenB 步然后 pA 和 pB 同步前进第一个相同的节点就是交点。为什么有效因为两个链表的公共部分长度相同差异只在前缀部分。把较长链表的前缀多走掉一段之后两个指针就同时到达距离交点相同的距离。public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA length(headA); int lenB length(headB); ListNode pA headA; ListNode 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 length(ListNode head) { int len 0; while (head ! null) { len; head head.next; } return len; }4.2 一个可以顺手做的优化在计算长度的过程中可以顺便记录两个链表的尾节点。如果两个尾节点不是同一个节点那么两个链表必定不相交可以直接返回 null省掉后续的指针移动。这个优化判断相交非常快尤其适合那种两个链表都很长、但明显不相交的场景。注意它只能作为前置判断不能代替后续逻辑因为即使尾节点相同也需要找到交点本身。4.3 三种方法放在一起比较方法时间复杂度空间复杂度代码理解难度是否修改链表哈希表O(mn)O(m)最简单否长度对齐O(mn)O(1)直观否双指针换路O(mn)O(1)需要数学证明否面试时我个人推荐先讲长度对齐法作为 O(1) 空间的方案因为它每一步的理由都很直白先算长度、再消差值、最后同步走。面试官容易跟上你的思路。双指针解法代码更短但在你讲清楚“为什么两个指针会相遇”之前面试官可能有点懵。你可以把两种都写一遍显得你对这道题理解足够深。5. 实战场常见错误与调试经验5.1 最典型的死循环场景我在本地练习时试过把重置逻辑写成这样while (pA ! pB) { if (pA null) { pA headB; } else { pA pA.next; } if (pB null) { pB headA; } else { pB pB.next; } }看起来和正确写法差不多但有一个陷阱在“一个指针为 null”的时候。假设 pA 先到了 null被重置为 headB。而 pB 还没到 null继续走。下一轮循环pA 可能还在走 B 链表的前半段pB 继续走自己的链表。这个时候两者路径并不是简单地相互换路而是每轮都在同步移动逻辑上其实是正确的。真正的死循环往往出现在另一种写法有人把 pA 重置放到 while 外面或者只对其中一个指针做重置操作。比如while (pA ! null pB ! null) { // 找交点 pA pA.next; pB pB.next; }这种写法在两个链表长度不同且不相交时循环会在某个指针先到达 null 后退出虽然不会死循环但会漏掉正确的交点。更隐蔽的问题是如果两个链表相交较长链表的前缀节点可能永远无法与另一条链表的路径对齐。为了避免这种问题我调试时会把循环条件固定写成 pA ! pB并且确保每一轮循环中两个指针都“要么往前走一步、要么重置到另一条链表的头”。这个口诀我背得很熟。5.2 空指针和边界用例清单代码写出来能跑不代表边界用例没问题。我刷这道题必测以下几组两个链表都为空返回 null其中一个链表为空返回 null两个链表只有一个节点且相交返回该节点两个链表只有一个节点且不相交返回 null两个链表长度相同相交点就在开头附近两个链表长度相差很大比如 A 有 1000 个节点B 只有 1 个节点且相交节点值重复但相交点在值相同的节点后面特别提醒节点值重复是最容易误导人的测试点。你在本地构造用例时故意让 A 和 B 的前缀里出现相同的值但相交点却在更后面的位置看看你的代码会不会因为“值相等”就提前返回。5.3 本地调试技巧LeetCode 的链表输入是用数组表示的但本地调试时手动构造链表比较麻烦。我常用的做法是写一个辅助函数def build_linked_list(values): dummy ListNode(0) cur dummy for v in values: cur.next ListNode(v) cur cur.next return dummy.next构造相交链表时先创建公共部分再分别接上两个前缀。比如公共部分节点是 c1 - c2 - c3A 前缀是 1 - 2B 前缀是 9那么 headA 就是 1 - 2 - c1headB 就是 9 - c1。调试双指针时打印每一步 pA 和 pB 的地址很有用。Python 里可以打印 id(pA)Java 里可以打印 pA 的 hashCode。我在模拟时发现两指针在“第二轮”相遇的过程非常直观打印地址能帮你确认是不是因为重置时机不对导致永远相等不了。6. 延伸与变体一道题带出整个链表相交家族6.1 变体一只判断两个链表是否相交不找交点如果只是判断是否相交最简单的做法是分别遍历到两个链表的尾节点然后比较尾节点是不是同一个节点。因为相交链表的尾节点必然是同一个。这个思路在长度对齐法里可以作为前置优化在面试中也可以单独出现。它把问题简化成“O(1) 空间下的尾节点比对”比求交点更容易解释。6.2 变体二链表可能带环呢难度完全不一样如果题目去掉“无环”这个约束情况会变得非常复杂。需要先判断两个链表各自是否带环找环入口然后分三种情况两个链表都不带环走普通相交逻辑一个带环一个不带环不可能相交直接返回 null两个都带环可能不相交也可能相交点在环外或环内处理“相交点在环内”时返回哪个节点都可以作为交点因为环内任意节点都可以看作相交点。这需要结合快慢指针找环入口、判环等知识已经不是一道简单题了。我刷 Hot100 时先掌握无环版本再单独刷“环形链表 II”补充带环找入口的方法这样循序渐进比较舒服。6.3 这道题和同专题题目的串联复习链表家族的题非常适合集中刷反转链表、链表中倒数第 k 个节点、合并两个有序链表、环形链表、删除链表倒数第 N 个节点、回文链表等。它们共同的基础操作就是遍历和指针移动很多题目互相之间能复用思路。160 题的核心价值在于“长度差消除”这个思想。这个思想也能迁移到数组、字符串的问题中比如找两个有序数组的公共后缀等场景。刷题的时候把一个思路拓展到多种题型比机械地刷十道题更有收获。我在网上看题解时经常看到有人把这道题和“LeetCode 周赛 430”、“073 爱吃香蕉的狒狒”这类题放在一起对比其实共同点是题目描述都挺生活化但真正解决时要先抽象出数学关系。160 题的数学关系是 acb bca073 的数学关系是二分枚举吃香蕉速度。用这种视角刷题你会慢慢发现不同题目之间的手感是互通的。7. 刷题之外我还想多说两句这道题我前前后后写了不下五遍每次重写都能发现新的理解角度。第一遍会背答案第二遍开始心里模拟指针的移动第三遍才真正理解为什么第二轮一定能相遇到第四遍我甚至能不用代码、只用口头给面试官讲清楚整个过程。我自己沉淀下来的一个经验是链表题别急着看题解先在纸上画图。把两条链表画出来标出交点然后用手指头模拟两个指针的移动走完一遍你自然就会写了。画图这一步能规避掉 80% 的“看懂了但写不出来”问题。推荐大家把这道题放进自己的“必须手写两遍以上”清单。第一遍照着思路写第二遍合上题解默写第三遍尝试给旁边的人讲解。能做到把 acb 和 bca 这个等式脱口而出的时候这道题才算真正拿下了。