刷 LeetCode 刷到链表题，十道里总有几道绕不开反转和相交这两个主题。今天要聊的#160 相交链表（Intersection of Two Linked Lists），是我印象里出现频率非常高的一道题，面试中常被用来做“暖场题”或者“二轮基本功”。题面很精简，给定两个单链表，找出它们相交的起始节点；但千万别被它表面的简单骗了，这道题的方案跨度从暴力、哈希到双指针、长度差，时间复杂度从 O(m×n) 一路降到 O(m+n)，空间复杂度也能从 O(m+n) 压到 O(1)。一道题能聊出来好几个层次，非常适合考察候选人对链表结构、指针操作、边界条件和复杂度优化的理解。
这篇文章我会直接以实战视角拆解这道题：先讲清楚命题意图，再逐个摆出五种可实现方案，核心部分是双指针法和长度差法的完整代码实现与数学原理，最后补充面试追问场景、测试用例设计和我自己踩过的坑。无论你是刚接触链表的初学者，还是准备跳槽想系统复盘的老兵，都可以直接拿这份笔记来用。
1. 先读懂题意：这道题到底在考什么
很多人在 LeetCode 上看到 #160，第一反应是“这不就是找两个链表共同的那个节点嘛，两层循环硬找就行了”。能跑通确实不假，可面试官想听的往往不是你最朴素的那个答案，而是你面对链表问题时能不能快速识别出“结构特征”和“约束条件”。这一节我们先把题目看透。
1.1 原题描述与核心信息
题目给两个单链表的头节点，要求返回它们开始相交的节点。如果没有交点，返回空值。题目明确要求不修改链表结构，并且整个判断过程只能基于引用（指针）相等——注意，这里不是比较节点里的数值，而是判断“同一个对象节点”。
举个例子：
- A：1 → 2 → 3 → 8 → 9
- B：4 → 5 → 8 → 9
从值为 8 的节点开始，后面就共享了。需要返回的正是值为 8 的那个节点对象本身。这里有个常见误解：如果两个链表只是某个节点的值相等，那不算相交；必须是同一个节点实例，指针相同才算数。
在代码里判断就一句话：
if nodeA == nodeB:而不是：
if nodeA.val == nodeB.val:很多初学的人在这里翻车。题目测试用例里经常会构造两个值相同但节点不同的链表，如果你按值判断，很容易误判。
1.2 题目暗含的约束与陷阱
这题最简单的暴力法，就是拿 A 的每个节点去 B 里逐个比对。思路毫无问题，但复杂度是 O(m×n)，在链表很长的时候基本上是挂掉的节奏。哈希法可以做到 O(m+n) 时间，但需要 O(m) 空间。真正考察的点在于：你能不能把这个空间复杂度优化到 O(1)，同时时间不退化。
另一个坑是“相交链表”这个词可能误导人。链表相交之后，是尾部共享，而不是像 “X” 字形那样交叉之后各走各的。单链表的每个节点只有一个 next 指针，所以一旦两个链表相交，从交点开始后面所有节点必然完全相同，这是单链表的结构铁律。理解这一点，很多后面的推导都会顺理成章。
还有一点：题目不要求你判断“是否相交”，而是要求返回“交点”。很多人在“判断有没有交点”这一步能答出来，一旦要返回具体节点就卡住了。原因无非是没想清楚怎么把两个长度不一样的链表对齐到同一起跑线。
2. 双指针法全解析：最优雅的解法，没有之一
双指针法在链表题里本来就是常客，#160 更是它的代表性应用。我第一次看到这个解法时觉得它就是“魔法”——两个指针明明从不同的链表头出发，走完自己的路再去走别人的路，居然就能在交点处相遇。后面仔细推导完才明白，这背后就是简单的路程相等。这一节我们把原理、代码、证明全部讲透。
2.1 双指针的核心思想：用“拼接”抹平长度差
假设链表 A 的非公共部分长度为 m，链表 B 的非公共部分长度为 n，两个链表公共部分长度为 L。也就是说：
- A 总长度 = m + L
- B 总长度 = n + L
如果两个指针分别从 A 和 B 的头节点出发，每次都走一步，当 A 指针走完 A 的全部 m + L 个节点时，它跳到 B 的头节点继续走；B 指针同理，走完 B 的全部 n + L 个节点后跳到 A 的头节点继续走。
那么，当 A 指针走到 B 链表上的交点时，它总共走了：
- A 的非公共部分 m
- 公共部分 L
- B 的非公共部分 n
也就是 m + L + n。
而 B 指针走到 A 链表上的交点时，总共走了：
- B 的非公共部分 n
- 公共部分 L
- A 的非公共部分 m
也就是 n + L + m。
这两个值完全相等。所以当两个指针都走完了“自己的链表 + 对方的链表”之后，它们一定在某个时刻同时到达交点。如果两个链表不相交，L = 0，它们会在同时走到各自“拼接链表”的末尾，也就是 null，此时循环自然退出，返回 null。
这就是为什么这个解法不需要事先知道两个链表的长度差，也不需要额外记录路径，天然就把长度差的问题消解掉了。类似把两个长度不同的跑道拼接成等长的闭环跑道——只要总路程一致，两个人总会相遇。
2.2 Java 与 Python 双指针实现
我把两套常用语言都写出来，方便你直接对比学习：
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode p = headA; ListNode q = headB; while (p != q) { p = (p == null) ? headB : p.next; q = (q == null) ? headA : q.next; } return p; } }class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: if not headA or not headB: return None p, q = headA, headB while p is not q: p = headB if p is None else p.next q = headA if q is None else q.next return p这里有一个细节值得注意：p和q走到各自链表末尾时，不是直接停在 null 上不动，而是要“跳到对方的链表头”。这步一旦写错，非常容易死循环。还有三元表达式的条件要写“第一次走到 null 时就切换”，不要写成“p 走到 null 之后返回 headA 再继续走”，这样逻辑就乱了。
2.3 为什么双指针一定能相遇：一个极简验证例
为了更直观，我们举个实际例子。设：
- A：1 → 2 → 3 → 8 → 9
- B：4 → 5 → 8 → 9
那么：
- 公共部分 L = 2（节点 8、9）
- A 的非公共长度 m = 3（节点 1、2、3）
- B 的非公共长度 n = 2（节点 4、5）
p 的行走路线是：1 → 2 → 3 → 8 → 9（到尾）→ 4 → 5 → 8，此时 p 走到了交点 8。
q 的行走路线是：4 → 5 → 8 → 9（到尾）→ 1 → 2 → 3 → 8，此时 q 也走到了交点 8。
两者同时到达。如果链表不相交，比如 A 是 1 → 2，B 是 3 → 4 → 5，那么 p 会走 1 → 2 → 3 → 4 → 5 → null，q 会走 3 → 4 → 5 → 1 → 2 → null，它们都会在走完 m + n 步之后同时指向 null，循环退出，返回 null。所以在双指针法里，不存在“相交链表死循环”“不相交卡住”这种问题，前提是切换逻辑写对。
3. 长度差法：先数人数，再对齐站位
双指针法虽然优雅，但有些同学第一次接触时理解困难。如果你属于“必须把每一步都推算清楚才敢下手”的类型，长度差法是更友好的一种方案。它的思路特别直白：两个链表长度不同，那就先把长链表的多余部分走掉，让两个指针站在离交点同样距离的位置，然后一起往前走，碰到第一个相同的节点就是交集。
3.1 长度差法的基本思路与复杂度分析
具体拆解成三步：
- 遍历链表 A，得到长度 lenA。
- 遍历链表 B，得到长度 lenB。
- 让较长的链表指针先走 |lenA - lenB| 步，然后两个指针同时前进，每次比较是否指向同一个节点。找到则返回；走到 null 则返回 null。
时间复杂度上，遍历两个链表各一次，加上对齐后最多遍历较短链表的长度，整体还是 O(m+n)。空间复杂度 O(1)，不需要额外容器。
这个方案有一个比双指针法更好的体验：如果链表不相交，两个指针同时走到 null，你能够很明确地意识到“它们是在同一条剩余路径上跑完的”。而双指针法的逻辑则需要你在脑内多做一层“拼接”模拟。
3.2 长度差法的 Java 实现
下面是我自己经常写的版本，有几点习惯很重要：
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = getLength(headA); int lenB = getLength(headB); ListNode p = headA; ListNode q = headB; // 让 p 指向较长链表的头，q 指向较短链表的头 int diff = lenA - lenB; if (diff < 0) { p = headB; q = headA; diff = -diff; } while (diff-- > 0) { p = p.next; } while (p != null && q != null) { if (p == q) return p; p = p.next; q = q.next; } return null; } private int getLength(ListNode head) { int len = 0; while (head != null) { len++; head = head.next; } return len; } }有两个细节值得单独说。第一，我习惯先把长链表指针统一交给p，避免后面在 if 分支里再写一遍 while 逻辑。第二，对齐之后接下来两个指针“同时走，边走边比”的阶段，务必在循环条件里带上p != null && q != null的判断，否则极端情况下会空指针异常。有些写法是直接while (p != q)，这样也能跑，但新人容易想不清楚什么时候循环会退出，所以我更推荐显式判空。
3.3 双指针法与长度差法的权衡对比
很多读者会问，既然双指针法代码这么短，为什么还要学长度差法？我的观点是，这两种方法不是替代关系，而是互补关系：
- 双指针法代码更短，不需要额外遍历求长度，面试时省时间；
- 长度差法思路更线性、更容易向面试官解释，适合做“第一个答案”，讲清楚后再自我优化成双指针法，会显得你思维更加递进；
- 双指针法有一个额外的理解门槛：它依赖“两个链表都走完一遍后切换”这个抽象假设，如果面试官追问“你凭什么觉得指针一定会同时到达交点”，你需要在两分钟之内给出准确的数学推导。长度差法则没有这种追问压力，因为它每一步都建立在直观的长度对比上。
所以你完全可以在面试时先用长度差法给出一个可运行版本，然后主动说“其实这道题还能压缩成无双遍历的双指针法，需要我补充吗”，这种展开方式比较自然。
4. 哈希法、穷举法等其他方案与边界细节
面试中并不是越高级的解法越适用。有些场景下哈希法是更容易写出来的保底方案，而穷举法则适合教学演示，但在真正的时间和空间限制下不推荐。这一节我把其他可行方案也聊清楚，并补充一些通用的边界条件处理技巧。
4.1 哈希表法：最容易想到的保底解法
思路非常直接：先遍历链表 A，把每个节点都放进一个HashSet里；然后遍历链表 B，每次检查当前节点是否已经存在于集合中。第一个命中的节点就是交点，遍历完都没命中说明不相交，返回 null。
import java.util.HashSet; public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { HashSet<ListNode> visited = new HashSet<>(); ListNode p = headA; while (p != null) { visited.add(p); p = p.next; } q = headB; while (q != null) { if (visited.contains(q)) return q; q = q.next; } return null; } }哈希法最大的优势是好写、不易出错，在数据量没那么大的时候完全够用。它适合作为你上手练习时的第一版答案，也适合在面试环节要求“15 分钟内写出一个能运行的版本”时作为稳妥选择。但空间复杂度是 O(m)，如果面试官直接问“能不能别用额外空间”，那就得往双指针或长度差方向走了。
4.2 穷举法为什么只配出现在教学场景
穷举法就是两层循环：拿 A 的每个节点和 B 的所有节点逐个比对，一旦发现相同引用就返回。代码极度直白，但时间复杂度 O(m×n)，一旦测试用例链表长度达到几千，运行时间就会明显变长。在 LeetCode 的判题环境里，这个方案通常也能过，因为官方测试数据还没狠到能卡爆它；但在面试现场，你要是只给出这一版，基本等于暴露了“没有复杂度意识”的短板。
我通常不建议任何人把穷举法当作最终答案提交，它的唯一价值在于让我理解“引用相等”这个概念时，可以用两层循环直观感受一下。
4.3 边界条件与空链表处理
这道题的边界条件就三个，但每一个都值得单独想清楚：
- 两个链表都为空：直接返回空，没有任何可比较的节点。
- 其中一个链表为空：不可能有交点，直接返回空。
- 两个链表不相交：所有方案都必须保证在这种情况下返回空，而不是抛异常或死循环。
在写代码时，如果你先把“任意一个头节点为空就返回 null”这个判断放在最前面，后面所有循环逻辑都不用担心空指针。又比如双指针法，如果开头不做判空，p == null时就会切到headB，如果headB也是 null，最后结果虽然还是 null，但中间很容易绕晕。加一个if (headA == null || headB == null) return null;能让你省掉不少调试时间。
还有一个值得注意的细节：不要试图修改链表的 next 指针，比如把尾节点接到另一个链表上形成环，再用快慢指针求交点。这种做法虽然理论上可行，但违反了题目“不修改链表结构”的约定，在你的代码被面试官检查时会被直接扣分。
5. 常见问题与排查技巧实录
写题过程中最容易出问题的其实不是算法本身，而是一些看起来不是问题的问题。我把自己调试这道题时踩过的坑和总结的排查方法整理成一份速查式清单，方便你对照自查。
5.1 死循环与空指针：双指针的经典翻车现场
双指针法最常见的错误就是把切换逻辑写成了下面这样：
// 错误示范 while (p != q) { if (p == null) { p = headA; // 这里应该切到 headB } else { p = p.next; } // q 同理 }如果两个链表不相交，p 走到 A 的尾部后会回到 A 的头节点，形成一个永不结束的循环。正确做法是走到 null 时切到对方的头节点，而不是切回自己的头节点。
另外，有些人在循环条件里写成while (p.next != q.next)，这在链表相交场景下等于多走了一步，很可能跳过交点节点，导致返回错误的后续节点甚至 null。我的建议是：从头到尾都只比较当前指针指向的节点对象，while (p != q)才是正确的循环边界。
5.2 面试官追问：你能证明双指针算法正确吗
这道题之所以适合面试，很大程度上在于它能引出“算法正确性证明”这个进一步考察点。我建议你在准备时准备一个标准回复版本，包含下面三个层次：
- 第一层：直观解释。两个指针分别走完两条链表的总路程相同，路程相同且速度相同，那么同一个时刻它们一定在相同位置相遇。
- 第二层：分情况讨论。相交时，它们会在交点相遇；不相交时，它们会同时在 null 相遇。
- 第三层：用具体例子验证。拿一个短链表和一个长链表快速跑一下，展示指针的每一步走向。
有了这三层，面试官基本不会再追问下去。真正危险的情况是你只会背代码，说不清为什么p从 A 跳转到 B 之后还能和q相遇，这是我在模拟面试中见过最多的卡壳点。
5.3 测试用例设计建议
自己手写完之后，不要只跑 LeetCode 自带的几个 case，建议自己构造下面这四类测试用例：
- 相交于链表中间的常规用例；
- 交点就是其中一个链表的头节点；
- 交点就是两个链表的尾节点；
- 两个链表完全不相交（包括长度相等和长度不等两种情况）。
构造方式很简单：先新建一个公共节点段，比如common = ListNode(8); common.next = ListNode(9);然后让 A 链表的尾节点指向common，B 链表的尾节点也指向common。记得在本地调试时不要打印节点地址之外的值，否则两个节点值相同但不是同一个对象时会误导你。
6. 实战经验总结：解题之外，面试还能怎么聊
如果只是把 #160 的三种解法背下来，面试能过，但多少有点可惜。这道题天然的延展性很强，面试官往往会在你答完之后顺势抛出几个变体，提前准备好会比现场临场推导轻松得多。
6.1 变体一：只判断是否相交，不找交点
这种变体其实更简单。只要看两个链表的尾节点是不是同一个对象就可以了，因为一旦相交，尾部必然完全共享。顺着这个思路，还能快速推导：如果尾节点相同，那么交点一定存在于前半部分。虽然代码简单，但面试官想看到的是你能不能用“结构铁律”去简化问题，而不是继续用双指针全套跑一遍。
6.2 变体二：如果有环，怎么找入口节点
“判断链表是否有环，并找到环的入口”是另一道面试常考题。它与 #160 的联系很微妙：相交链表中每个节点只有一个 next 指针，一旦相交就不可能形成环；但如果你用快慢指针去处理链表问题，这两道题的底层指针切换逻辑其实是相通的。有些面试官会把 #160 和“环形链表 II”捆绑起来问，本质是在考察你能否从一个具体链表操作中抽象出通用的“双指针交通规则”。提前把题组串联学习，比单刷一道题的收获大得多。
我的建议是：把 #160 当作一个锚点，往前后各延伸两道题。往前是“删除链表倒数第 N 个节点”，考的是通过双指针位置差来定位；往后是“环形链表 II”，考的是快慢指针的数学证明。串在一起复习，你对链表双指针题型的掌控力会提升一个档次。
最后再分享一个我在实际刷题中验证过很多次的体会：链表类的面试题，最忌讳“一上来就写最优解”。哪怕你心里已经想到了双指针，也建议先用一两句话讲一遍暴力思路，再说“这段代码时间复杂度太高，我们可以用哈希优化，再进一步可以做到常数空间”。这样面试官能从你的叙述里看到完整的思考轨迹，而不是只看到最后那个正确答案。#160 这道题的设计本来就非常巧妙，它给了你足够的台阶去展示“从 O(m×n) 到 O(m+n) 时间、O(m+n) 空间到 O(1) 空间”的完整优化链路，把这条链路讲清楚，远比默默写出三行代码更有价值。
