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

我最近在整理自己的每日一题笔记，正好写到相交链表这道经典题。它是LeetCode第160题，也是链表模块里面试出现频率极高的一个。原题有很多马甲，比如找两个单链表的交点、判断两条链表是否合并过，但内核都是同一件事：给定两条单链表，找到二者开始相交的那个节点，如果没有任何交点，返回null。这题非常适合正在刷算法题准备面试的人，也适合刚学链表不久、想拿一个典型题目练手的新手。它考察的东西很实在：你对链表结构的理解是不是停留在“值相等”的层面，以及你懂不懂双指针这类遍历技巧。

我第一次做这道题时翻了个很经典的错误——以为找到值相等的节点就是相交，结果被测试用例教做人了。今天把这道题从审题到最优解完整拆一遍，顺便把那些常规题解里不会写的坑都列出来。

1. 先把题读明白：相交链表究竟在求什么

1.1 题目说人话版

题目原文有一大段背景设定，翻译成人话就是：给你两条单链表，它们可能在某个节点之后完全共用一条链，像字母Y那样先分开后合并。你要找到那个“分叉合流点”，也就是第一个被两条链表共同拥有的节点。如果没有这种节点，就返回null。

需要注意的是，这个“共同拥有”在链表里必须理解成节点本身被同时引用，也就是两个链表走到了同一个内存地址，而不是两个节点恰好存了相同的值。底层逻辑是：单链表的节点里只有一个next指针，指向下一个节点。一旦两个指针指向同一个节点，那么从这个节点开始，后续所有节点必然完全一致，因为再也分不开了。这也是为什么相交链表在图上一定是Y字形，而不可能是X字形——X字形意味着两个节点合并又分开，这在单向链表里根本做不到。

1.2 最常见的审题翻车点

我见过很多刷题的人在这道题上栽跟头，包括我自己，本质上都是没分清“值相同”和“节点相同”。举个例子：

链表A是 1 -> 3 -> 5，链表B是 2 -> 3 -> 6。这两个链表里都有值为3的节点，但它们各自是独立分配的节点，只是内容恰好相同。用代码表示就是nodeA.val == nodeB.val，但nodeA和nodeB指向不同的地址。题目要的不是这种“貌似相交”，而是nodeA == nodeB这种“真·同一个节点”。

为什么这个区别这么关键？因为如果你按值去判断，只靠几个简单用例根本测不出来，但提交后就会遇到各种构造好的测试数据。面试现场如果写错这个逻辑，面试官一眼就能看出来你理解的是“数组”而不是“链表”。

还有一个容易忽视的点：题目默认这两个链表都没有环。LeetCode原题的说明里明确规定了这一点。如果你在面试中被追问“如果有环怎么办”，那是另一道变体题，后面我会单独讲一下处理思路。

1.3 这个考点为什么被面试官偏爱

相交链表在面试中受欢迎，不是因为算法本身有多高级，而是因为它能把候选人的基础功底问得很透。考察点至少有三个：

• 第一个，你知不知道链表节点是由地址/引用维系的，而不是值。这是数据结构的底层认知。
• 第二个，你愿不愿意主动分析时间和空间复杂度。题目很容易写出一个O(n*m)的暴力做法，但好的解法需要把复杂度降到O(n+m)。面试官就是想看你能不能主动优化。
• 第三个，你懂不懂双指针这种“无额外空间的遍历技巧”。这是链表题的常青考点，会了这道题，后面做环形链表、删除链表倒数第N个节点都会顺手很多。

所以这道题看起来是“每日一题”，其实是性价比很高的题目。

2. 最容易上手的哈希集合法

2.1 思路一句话版本

先把一条链表的所有节点存进一个哈希集合，再遍历另一条链表，第一次遇到“已经在集合里”的节点，那就是交点。如果整条遍历完都没有，说明两条链表不相交。

为什么哈希集合可行？因为集合里存的是节点引用，判断时也是按引用去比较，天然满足“同一个节点”这个精确语义。而且哈希集合的查找平均是O(1)，所以整体性能不差。

2.2 代码实现与逐步拆解

用Python写起来非常直白：

def get_intersection_node(headA, headB): visited = set() cur = headA while cur: visited.add(cur) cur = cur.next cur = headB while cur: if cur in visited: return cur cur = cur.next return None

拆开看就三步：

第一步，从headA出发，把沿途每个节点都放进set，注意放的是节点对象本身，不是cur.val。 第二步，从headB出发，每走一步都问一句“这个节点在不在刚才那个set里”。 第三步，如果B链的某个节点命中，直接返回；如果B走完都没有，返回None。

2.3 哈希法的适用场景与局限

哈希法的优点是逻辑简单，不容易错，适合作为面试时的“第一版答案”。你完全可以先跟面试官说：我先用哈希集合做一个最容易理解的版本，再考虑优化空间。

它的局限也很明显：额外的空间复杂度是O(n)，需要保存一条链的全部节点。在面试里，面试官大概率会追问一句“能不能把空间复杂度降到O(1)”。这时候就能顺理成章地引出双指针解法。

这里还有一个实操小技巧：在判断“cur in visited”之前，不需要对cur判空，因为当cur为None时，None不在集合里，而while循环的条件也保证了cur不会是None，除非headB本身就是空链表。如果headB是空链表，第二个while压根不进入，直接返回None，结果也是对的。

提示：哈希集合必须存节点，不要存节点值。存节点值的代码跑再多次也过不了完整的测试用例。

3. 最优解：用双指针破解相交链表的完整推演

3.1 核心思想：把两条路接成一条路

双指针解法是这道题最精彩的版本，同时也是网上流传最广的版本。我第一次看到这个解法时，第一反应是“这是什么魔法”，后来拿两个链表手动推了两遍，才真正明白它背后的数学逻辑。

逻辑是这样的：维护两个指针pA和pB，分别从headA和headB出发。两个指针每次各往前走一步。区别在于，走得快的那个指针如果走到了链表尾部（达到null），就从另一条链表的头部重新进链表继续走；另一个指针同理。这么循环往复，直到两个指针相遇。相遇的那个节点，要么是交点，要么是null。

用一句话概括：每个指针最终走完的路程，都是链表A的长度加上链表B的长度。在这个“同步总路程”的前提下，两个指针天然消除了长度差。如果两条链表有交点，它们必然会在交点相遇。

3.2 链表长度与节点数的数学关系

假设链表A的长度是L1，链表B的长度是L2，相交部分长度是C。这里C是两条链共享的那一段节点数。

• 如果从headA出发，先走完自己的L1步，再切到headB继续走，想走到交点，还需要走多少步？答案是L2 - C步。因为在B链表里，交点之前的节点就是L2 - C个。
• 所以pA从出发到交点，一共走了 L1 + (L2 - C) 步。
• 如果从headB出发，先走完自己的L2步，再切到headA继续走，想走到交点，还需要走 L1 - C 步。
• 所以pB从出发到交点，一共走了 L2 + (L1 - C) 步。

两个式子算一下：

L1 + L2 - C = L2 + L1 - C

发现是完全相等的。这就解释了为什么两个指针一定会在同步推进的过程中于交点相遇。它们虽然起点不同、各自先走的长短也不同，但只要是“先走完自己的，再去走别人的”，总步数就会被拉平。

如果两条链表根本不相交，也就是C = 0，上面的计算会变成：pA走了L1 + L2步后停在null，pB走了L2 + L1步后也停在null。因为空指针和空指针是相等的，循环照样会终止，结果返回null，不会死循环。

3.3 具体推演：相交链表双指针全过程

光看公式还是不够直观，我特意构造了一个具体的链表对，把每一步的指针位置写出来，你就明白它有多优雅了。

构造如下：

链表A：a1 -> a2 -> c1 -> c2 -> c3 -> null 链表B：b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> null

这里的c1就是交点。链表A长度是5，链表B长度是6，公共部分是c1、c2、c3，公共长度C = 3。

双指针同步推进，每一轮变化如下：

看最后两行，虽然两个指针之前的“身世”完全不同，但在第9轮双双站到了c1上。pA经历了完整的链表A，又走过了链表B交点和交点之前的b1、b2、b3；pB经历了完整的链表B，又走过了链表A交点和交点之前的a1、a2。二者总步数完全相同，交点也完全相同。

3.4 不相交时为什么也不会死循环

很多第一次接触这个解法的人会担心：如果不相交，两个指针会不会永远互相追不上？答案是并不会，因为最后都会变成null。

同样做一个简单推演。链表A：a1 -> a2 -> a3，链表B：b1 -> b2。两者长度分别是3和2。

两个指针最终在null处相等，循环正常终止，返回null。因为pA一共走了L1 + L2 + 1个位置（包括最后那个null），pB也一样，步数一致，双方同步抵达终点。

这里有一个细节值得注意：指针从null跳到另一条链表头部这件事，本质上是把“两条链表拼接起来”。pA走的路径等价于A链表接到B链表后面，pB走的路径等价于B链表接到A链表后面。如果相交，拼接后的两条长链从交点开始共享相同后缀；如果不相交，拼出来的两条长链也一样长，最后同时走到null。

3.5 代码实现（Python / Java 双版本）

双指针代码非常短，但正因为短，初学者容易背错。我在这里列出两个常用版本。

Python版本：

def get_intersection_node(headA, headB): 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

Java版本：

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.next判断是否到达尾部，千万别忘记当pA已经为null时也会走到这个分支，所以要先判断pA本身是否为空。

第二个是跳转时机。pA变到null的下一轮才跳转到headB，而不是在最后一个有效节点时就跳转。换句话说，链表A完全走完，指针变成null之后，下一步才从headB重新开始。这样保证总路程确实是L1 + L2，而不会因为提前跳转导致路程变短。

第三个是while条件。循环条件必须是pA != pB，而不能是pA.next != pB.next。因为两个链表不相交时，最终相遇的位置是null，如果用next去判断，会在pA或pB为null时直接报错。

注意：这个解法在LeetCode上的时间复杂度是O(m + n)，空间复杂度是O(1)，属于题目要求范围内的最优解。

4. 其他常见思路与解法对比

4.1 长度差法

除了双指针，还有一类常见解法叫“长度差法”，在工程场景和教学里也很常出现。思路不复杂：先分别求出两条链表的长度，然后让较长的链表指针先走长度差这么多步，把两条链表的“起跑线”对齐，再同步往前走，第一次相遇的节点就是交点。

Python代码是这样的：

def get_intersection_node(headA, headB): def get_length(head): length = 0 while head: length += 1 head = head.next return length lenA, lenB = get_length(headA), get_length(headB) pA, pB = headA, headB diff = abs(lenA - lenB) if lenA > lenB: for _ in range(diff): pA = pA.next else: for _ in range(diff): pB = pB.next while pA != pB: pA = pA.next pB = pB.next return pA

这个解法的优点是逻辑非常直观，容易向面试官解释，也不会出现“为什么两个指针能相遇”这种让人挠头的疑问。缺点是代码相对长，需要多写一个求链表的函数，而且要知道两条链表的长度后才能开始对齐。

从面试的角度讲，你可以先讲长度差法，再讲双指针法，展示你思路的递进过程。两种解法的复杂度都是O(m + n)时间，O(1)空间，实际运行效果几乎没有差别。双指针的代码更短，但理解门槛更高；长度差法的代码更长，但逻辑更接地气。

4.2 解法对比表

我把这道题常见的几种方案整理成一个表格：

4.3 一个容易被忽略的坑：有环链表

前面说了，LeetCode原题默认链表无环。但面试官很可能追问一句：如果两条链表各自可能有环呢？这就变成了进阶题。

有环情况下，处理方法完全不同。标准套路是这样的：

第一步，分别判断两条链表是否有环。方法就是快慢指针，一个走两步、一个走一步，如果会相遇说明有环，并且还能找出入环点。 第二步，如果两条链表都没有环，就用上面任意一种常规解法。 第三步，如果一条有环、一条无环，直接返回不相交。 第四步，如果两条都有环，又分两种情况。一种是在入环之前就合并了，那就用长度差法或双指针先找合并点，但在处理时得注意避开环；另一种是各走各的环，那就分别找到入环点后，看两个入环点是否在同一个环上，如果不在同环，说明不相交，如果在同环，交点可以是任一入环点。

我建议一般面试场景下，先把无环的常规解法讲清楚，再提一句“如果链表有环，可以先通过快慢指针找到入环点再分情况讨论”，这就足够展示能力了。不用强行把有环的完整代码背下来，除非候选人明确要求深入学习。

5. 面试场景实战与避坑清单

5.1 拿到这道题的正确思考顺序

刷题和面试不一样，面试时面试官更看重你的思考过程，而不是你背了哪个模板。我建议拿到题目后按这个顺序组织思路：

第一步，向面试官确认几个边界条件：链表是否允许为空？链表是否有环？是否允许修改原链表结构？这几句话能体现你的工程意识。

第二步，先给出最朴素的想法。可以说：最粗暴的做法是固定A的每个节点，依次遍历B的每个节点，但这样是O(m*n)，不太行。

第三步，提出用空间换时间的方案，也就是哈希集合。在纸上画出两条链表，标出交点，说明先用set存A链节点，再遍历B链命中第一个交集节点。这样做的时间是O(m+n)，额外空间是O(n)。

第四步，也是关键一步，主动说：我还能把空间优化到O(1)。这时引出双指针，并口头解释两条指针走的路程相同，最后必然在交点或null处相遇。

这样下来，面试官会看到你完整的问题解决链路：暴力 -> 时空权衡 -> 最优解，这比直接背出双指针代码要加分得多。

5.2 我踩过的和见过别人踩的坑

这部分是我最想写的内容。双指针解法代码很短，但它坑人的地方也不少。

第一个坑是“用值比较而不是引用比较”。我见过有人写出if (pA.val == pB.val) return pA;这样的代码，结果遇到值重复的测试用例就挂了。再次强调，链表节点之间的相等必须用节点本体，也就是pA == pB，因为只有地址相同才是真正共享。

第二个坑是“跳转时机错误”。正确写法是当pA走到null后再跳转到headB。如果写成pA.next == null时跳转，就会少走最后一个节点，导致总路程不对。这个bug很隐蔽，单测几组数据可能都测不出来，但遇到两条链表长度差比较大的例子就会出错。

第三个坑是“忘记处理空链表”。虽然空链表时循环也能正常工作，但最好在函数开头就明确判空，返回null。这不只是为了正确性，也是给面试官看的代码洁癖。另外，有些编程语言里对null取属性会直接抛出异常，提前判空是更稳妥的习惯。

第四个坑是“只背代码不理解推导”。面试官如果让你解释“为什么双指针能够在交点相遇”，你答不上来，那就很尴尬。我见过不少候选人能默写出代码，但一问原理就说“我看别人这么写的”。这种回答在面试中掉分很快。所以不管是为了面试还是为了真正提升技术，上面3.2小节的数学推导一定要能自己讲一遍。

第五个坑是“调试时犯了低级错误”。链表这种结构调试起来比数组麻烦，因为它不是连续内存，没法一目了然。我自己的习惯是在本地测试时给每个节点打上唯一标记，或者用对象的id值作为区分，这样才能清晰地看到pA和pB到底走的是哪条路。

5.3 常见问题速查表

我把这道题可能遇到的疑问集中成一个速查表，平时复习时扫一眼就够了：

5.4 一个容易延伸出来的面试追问

面试官如果对这道题比较满意，大概率会顺带问一句“你还知道哪些双指针的链表题”。这时候如果你能列举出环形链表检测、删除链表倒数第N个节点、寻找链表中间节点，就能展示出你确实掌握了这一类技巧，而不是只会背一道题。

我自己总结的规律是：链表题里的双指针，本质上是在控制“相对速度”或“相对路程差”。相交链表用到的是路程差，环形链表用到的是速度差，删除倒数第N个节点用到的是距离差。你看，思路是同一个体系，题却能变化出很多种。

最后再分享一个小技巧：本地练习时，别只盯着LeetCode那个图形界面。你完全可以自己构造节点指针来做实验。比如Python里可以定义两个节点对象，再把后一个节点的next指向前一个节点，通过打印节点的id值来确认相交；Java里可以打印System.identityHashCode(node)，也能达到同样效果。手动推演两遍，比看十篇题解都有用。

这道题我刷了不止一遍，每次做都还能发现一点新东西。双指针解法看着简单，但能把其中的路程差原理讲到让人点头，才算真正掌握了。如果你目前还在为链表题发愁，不妨就从相交链表开始，用它把节点的引用语义和双指针思路一次吃透。