相交链表双指针与哈希集合解法：从引用比较到边界测试

很多人刷算法题有个误区：总觉得难题才值得反复琢磨，简单题看一眼答案就划走。但“相交链表”这道题，在 Hot 100 里躺了很久，难度标着 easy，实际上非常值得掰开了揉碎了讲一讲——它考的不是你会不会遍历链表，而是你有没有建立“链表是引用结构，不是值结构”这个意识。

我最近在整理算法入门题单时，又把这道题翻了出来。它表面上只是“找两个链表的交点”，背后却牵扯到哈希表的使用时机、双指针的相遇逻辑、边界情况的处理，以及链表类题目最容易被忽略的测试环节。这篇文章就把我梳理过的思路、写过的代码、踩过的坑一起聊一聊，无论是准备面试还是补基础，这一道题吃透，链表类的很多问题都会有豁然开朗的感觉。

1. 题目拆解：看似简单的“找交点”到底在考什么

1.1 原题描述与核心考点

题目描述很简短：给你两个单链表的头节点，找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

图我就不画了，但你要在脑子里形成一个关键印象：相交不是“两个链表在某处值相等”，而是“两个链表从某个节点开始，后面的所有节点完全重合”。这意味着两个链表共享的不只是数据，而是同一批节点对象。用专业一点的话说，就是它们从相交点开始，指向同一段内存地址。

这个描述里藏着这道题真正的考点：

• 链表节点的比较是引用比较，不是值比较。两个节点即使 val 相同、next 相同，只要不是同一个对象，就不算相交。
• 要能处理“不相交”的情况，不能死循环。
• 需要考虑两个链表长度不一致的问题，否则你同时从头遍历时，根本对不齐。

很多新手在这里犯的第一个错，就是想当然地比较 headA.val == headB.val，然后继续往后走。这是把链表的逻辑关系和数组的比较方式混为一谈了。数组里值相同就可以认为“内容相同”，但链表里的“相同”指的是“引用相同”，这决定了你找交点的本质是“找两个引用链的汇合处”。

1.2 为什么这道题能进 Hot 100

Hot 100 收录的是面试里出现频率高、且能较好考察数据结构和算法思维的题目。“相交链表”虽然难度是 easy，但它在面试中能衍生出好几个层次的考察点：

第一层，考察你会不会最基本的哈希表思路。遍历第一个链表，把节点引用存进集合，再遍历第二个链表，第一个遇到的已存在节点就是交点。这一层只要你知道哈希表是什么就能写出来。

第二层，考察你能否写出空间复杂度 O(1) 的解。这时候需要双指针，思路并不难，但很多人没见过就想不出来——两个指针分别从两个头节点出发，走完自己的链表后切换到对方的链表继续走，最终会在交点相遇。这个技巧在“链表找环”“链表交点”“链表合并”这类题里反复出现，属于高频套路。

第三层，考察你对代码细节的掌握。循环条件怎么写才不会死循环，不相交的情况怎么退出，空链表怎么处理，这些都是面试官会追问的地方。

所以这道题不是“背答案”就行的题，它是把哈希、指针、边界处理、复杂度分析都装进了一个看似简单的壳子里。对面试来说，它是个高效的“筛子”。

2. 解法一：哈希集合法，最稳妥的基准答案

2.1 思路说明与代码实现

哈希集合法的思路非常直白：先遍历链表 A，把所有节点引用放入一个哈希集合（HashSet）。然后遍历链表 B，逐个检查当前节点是否已经在集合里。如果在，说明这个节点就是相交点，直接返回它；如果遍历完 B 都没有遇到，说明两个链表不相交，返回 null。

这是一个“拿空间换时间”的思路。时间复杂度是 O(m+n)，其中 m 和 n 是两个链表的长度——先遍历一遍 A，再遍历一遍 B，所以是线性级别。空间复杂度是 O(m)，因为你需要存下链表 A 的全部节点引用。

来看一段 Python 代码示例：

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

这段代码很朴素，但有一个小细节值得注意：seen存的是节点对象，不是节点的值。如果存的是值，那么两个不同链表里恰好有两个值相同的节点就会引发误判，整道题的逻辑就崩了。这也是我前面强调“引用结构”的原因——哈希集合法的正确性完全建立在存引用这个前提上。

2.2 为什么选择哈希集合而不是哈希表

有人可能会问，用字典（HashMap）行不行？可以，但你只需要知道“这个节点有没有出现过”，不需要关联任何额外信息，所以用集合（Set）就足够了。多存一个 Key-Value 对，既浪费内存，又让语义不清楚。

再补一个工程上的小细节：别用数组存节点再遍历查找，那样每次查找都是 O(n)，整体会退化到 O(m*n)，在大链表上直接超时。哈希集合的查找是 O(1)，这是它在这个场景下的核心优势。

哈希法适合作为面试时的第一步回答——它容易写、容易验证、不容易出 bug。面试官让你做这题时，你先把哈希方案讲清楚，展示你理解了“引用比较”这一层，然后对方大概率会追问“能不能优化空间复杂度”，这时候就轮到双指针方案登场了。

3. 解法二：双指针法，空间 O(1) 的经典技巧

3.1 “互相走对方的路”为什么能相遇

双指针法的代码非常短，但第一次看的人往往要琢磨一阵子才能信服。

设置两个指针 pA 和 pB，分别指向 headA 和 headB。然后同步移动：pA 每走一步，pB 也走一步。如果 pA 走到了链表末尾（null），就把 pA 重置到 headB；同样，pB 走到了链表末尾，就把 pB 重置到 headA。继续同步移动。当 pA == pB 时，如果两个链表相交，它们相遇的位置就是交点；如果两个链表不相交，它们最终会同时停在 null 处。

代码长这样：

def getIntersectionNode(headA, headB): pA, pB = headA, headB while pA != pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA

为什么这个办法有效？我来拆解一下核心逻辑。

假设链表 A 的长度为 m，链表 B 的长度为 n，它们的公共部分长度为 c。那么：

• A 中不相交的部分长度为 a = m - c
• B 中不相交的部分长度为 b = n - c

pA 从 headA 出发，先走完 A（共 m 步），然后切到 headB 继续走。pB 从 headB 出发，先走完 B（共 n 步），然后切到 headA 继续走。

当 pA 走过的总步数为 a + c + b 时（也就是走完 A 以后，又在 B 上走了 b 步），它正好走到交点。与此同时，pB 走过的总步数为 b + c + a，它从 B 切到 A 后，也走了 a 步，同样走到交点。由于 a + b + c 在两个指针的计算中是同一个数，它们经过的步数一致，所以会在同一时刻到达同一个节点。

这里有个更直观的类比：两个人分别从一条环形的两个入口出发，一个跑得快一个跑得慢，但只要都绕着环形跑，总是在某处相遇。双指针的思路本质上就是把两个链表“拼接”成了一个虚拟的循环结构——pA 走完 A 再接 B，pB 走完 B 再接 A，这样无论两个链表原本长度差多少，两个指针总会在交点对齐。

3.2 两种特殊情况下的行为推演

第一种情况：两个链表不相交。设 A 长度为 m，B 长度为 n。pA 走完 A（m 步）后切到 B，再走 n 步，总共走 m+n 步；pB 走完 B（n 步）后切到 A，再走 m 步，也总共走 m+n 步。于是在最后一步，两个指针同时到达 null——因为两个链表走完自己的全部长度再去走对方的全部长度，终点都是 null。循环条件 pA != pB 失灵，循环退出，返回 null。这正好符合“不相交返回 null”的要求。

第二种情况：有一个链表为空。比如 headA 是 null，那么 pA 初始就是 null。pB 指向 headB，pA != pB，进入循环，pA 已经是 null 了，所以会被重置为 headB。pB 如果走到了末尾，会被重置为 headA（也就是 null）。最终两个指针都会收敛到 null，循环退出，返回 null。这个过程逻辑上自洽，没有死循环的风险。

但这里有一个非常容易踩的坑：如果把条件写成了 while pA and pB，那就完蛋了。因为遇到不相交的链表，pA 或者 pB 一旦走到 null，循环就直接退出，返回 null——看上去好像“碰巧”也对了？不对，如果链表 A 比链表 B 短很多，pA 先到 null，循环退出，但此时根本还没检查完链表 B，你返回 null 是错的。所以记住：正确写法是 while pA != pB，并且循环体里通过 if pA 来判断是否切换链表。用“指针是否为空”来判断切换，而不是用“当前链表是否走完”来判断。

3.3 双指针法与哈希法的取舍

双指针法的空间复杂度是 O(1)，时间复杂度是 O(m+n)，整体上和哈希法一样线性，但省掉了额外存储。面试场景里，它通常是更被青睐的答案。

但不要因此就轻视哈希法。我个人的建议是：面试时先讲哈希法，快速给出正确解，然后主动提出“我可以优化到 O(1) 空间”，再展示双指针。这样既显得思路清晰，又展示了你对算法优化的敏感度。只背一个双指针答案上去，万一遇到“为什么这样能相遇”的追问，讲不清楚，反而容易翻车。

4. 工程细节与多语言实现要点

4.1 C++ 与 Java 版本的等价写法

Python 代码看着清爽，但很多公司的面试环境是 C++ 或 Java。我顺手把另外两个版本的写法也整理了，方便对照。

C++ 版本：

class Solution { public: ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA = headA; ListNode* pB = headB; while (pA != pB) { pA = (pA == nullptr) ? headB : pA->next; pB = (pB == nullptr) ? headA : pB->next; } return pA; } };

Java 版本：

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA; ListNode pB = headB; while (pA != pB) { pA = (pA == null) ? headB : pA.next; pB = (pB == null) ? headA : pB.next; } return pA; } }

这三个版本的核心逻辑是一模一样的，区别只在语法层面。要注意的是，C++ 和 Java 里“引用”这个概念更加显式，节点比较的值天然是引用地址，所以直接用!=比较就对了。

4.2 一个容易被忽视的问题：不要修改链表结构

有些思路（比如先遍历一个链表，标记每个节点，再遍历另一个）很容易让人想到“给节点加一个 visited 标记”。如果是自己定义一个节点结构，加一个字段无可厚非；但在 LeetCode 这类题目环境里，你拿到的 ListNode 是定义好的，不允许你往里面塞额外字段。更重要的是，不要在题目要求之外去修改链表结构，比如把相交点之后的 next 断开再重接。

这一点在真实工程里同样是红线。链表往往被多个地方引用，你为了算法运行方便修改了某个节点的 next，可能会导致其他模块拿到的链表变得残缺。所以写这类题时，养成一个习惯：遍历可以，复制可以，但尽量不要改动链表本身的拓扑结构。除非题目明确要求你“原地修改”，否则保持输入数据的原样是基本素养。

4.3 为什么循环条件不能简写为 while (pA)

再来强调一次这个坑。有一种看似“更短”的写法是这样的：

while pA: # 各种逻辑

在这种写法里，只要 pA 不为空就一直跑。问题是：如果两个链表不相交，pA 不会永远非空，但可能在真正结束之前就退出循环，导致错误结果。正确解法里，循环退出条件必须同时依赖 pA 和 pB 的相对关系，而不是单独依赖某一个指针的非空状态。

我把这类错误总结成一个排查清单，方便你在代码写完以后自查：

• 循环退出条件写的是pA != pB吗？不是的话，优先怀疑。
• 指针切换用的是pA = pA.next if pA else headB吗？确认一下 pA 为 null 时是切到另一个链表头，而不是停留在 null。
• 如果两个链表长度相差很大，你手动模拟一遍流程了吗？这个非常管用，纸上画一画就暴露问题了。

5. 测试与验证：链表类题目最容易翻车的地方

5.1 如何正确构造测试数据

链表题和数组题有一个本质区别：数组可以直接在测试代码里写一长串字面量，链表得先写一个构建函数。很多人在刷题时忽略了测试环境的搭建，直接提交到平台上，失败了也不知道问题出在哪个用例上。我在本地调试时，一般会写一个工具函数，把数组转换成链表，把链表再转换回数组，这样测试用例写起来就像数组一样直观。

相交链表的测试数据比普通链表要麻烦一点，关键在于“共享节点”。你不能简单地用两个独立的链表去模拟相交，因为在测试代码里，两个链表的相交点在内存里必须是同一个对象。具体做法是：先构造一个公共链表 tail，再把 tail 接到两个不同的头节点后面。

以 Python 为例：

class ListNode: def __init__(self, x): self.val = x self.next = None def build_list(arr): dummy = ListNode(0) cur = dummy for v in arr: cur.next = ListNode(v) cur = cur.next return dummy.next, cur # 返回头节点和尾节点 # 构造相交链表：A = [1,2,3] 与 B = [4,5] 共享 [6,7] tail_head, tail_tail = build_list([6, 7]) a_head, a_tail = build_list([1, 2, 3]) b_head, b_tail = build_list([4, 5]) a_tail.next = tail_head b_tail.next = tail_head

这样构造出来的 A 链表是 1->2->3->6->7，B 链表是 4->5->6->7，相交点就是值为 6 的那个节点。你在测试辅助函数里还要写一个找节点的方法：给定头节点和目标值，遍历返回第一个值匹配的节点引用，然后断言算法返回值是否等于这个节点对象。

这里有一个很隐蔽的问题：如果链表中存在重复值，用“值匹配”来找预期节点可能会命错对象。所以在写测试断言时，最好的方式是直接比较节点对象（assert result is expected_node），而不是比较result.val。一旦你开始用值比较，就又把链表题做回了数组题，测试的有效性会大打折扣。

5.2 测试用例设计清单

我每次写链表题，都会先列一份用例表格，覆盖正常、边界、异常三类情况。对于相交链表，至少要覆盖下面这些场景：

第 5、6、9 三条尤其容易被忽略。很多人测试链表题时习惯性只测非空情况，结果一提交，有几个边界用例直接报错。我自己的习惯是，每次写完算法，先把空链表、单节点链表这些极端情况摆上去跑一遍，确认不报错，再做常规功能用例。

5.3 我在测试时实际踩过的几个坑

第一个坑，是构建共享链表时不小心“创造”了意外的相交点。比如我先 build 出 A 的完整链表，再 build B，然后直接把 A 的某个中间节点接到 B 的尾部。这个操作本身没问题，但如果你在构建 B 时复用了 A 里的某个节点对象，比如不小心把b_tail.next = a_node写成b_tail = a_node，那 B 就只剩三个节点，语义完全变了。这种情况下算法可能“正确”返回了错误节点，但你很难察觉，因为打印出的 val 可能碰巧符合预期。所以我后来在测试辅助函数里会打印出每个节点的内存 id，排查这种引用错乱的问题。

第二个坑，是“值相同但节点不同”导致的手动模拟误差。我在纸面上推导算法时，习惯把链表写成值和箭头，比如 1->2->3->6->7。这种表达方式默认了“值相同就是同一节点”，但真实代码不是这样的。你构造两个值序列完全相同的独立链表，算法会正确地返回 null，而你在手写推导时却可能会误以为它们“应该相交”。所以我在推演双指针过程时，会特别标注出哪些节点在内存中是同一个对象，避免被值的表象欺骗。

第三个坑，和性能测试有关。虽然这道题的时间复杂度是 O(m+n)，但如果你用 Python 的in列表操作去替代哈希集合，在最坏情况下（链表很长且不相交），总耗时可能会达到 O(m*n) 级别。我用一个数万节点的链表测过，列表版本跑了十几秒都跑不完，集合版本瞬间出结果。这个不是题目解法本身的问题，而是测试代码里辅助实现的问题，但如果你没单独测过，很容易误判成“算法太慢”。

6. 常见问题与面试追问的避坑指南

6.1 高频错误速查表

我把刷这道题时容易踩的坑整理成了一个速查表，适合你在写完代码后逐条对照排查：

这其中的第一条非常关键。我见过不少人在写双指针时，先执行pA = pA.next，再判断pA == pB，结果把相交节点往后移了一位。正确的顺序是：先判断pA == pB（初始状态可能就是相交点，比如两个链表头节点就是同一个），然后才考虑移动指针。

6.2 面试官常追问的三个问题

第一个追问：这个双指针解法有什么前提条件？你要答出来，它要求两个链表是无环的。如果链表里有环，双指针的“走完切换到另一个链表”策略会失效，因为你永远走不到链表末尾。处理带环情况的思路完全不一样，一般需要先判断是否有环，这也是另一道经典题。

第二个追问：如果题目要求返回相交点的索引下标，而不仅仅是节点引用，你怎么做？这时候你需要在遍历时记录每个节点的位置信息，哈希法天然支持这一步，双指针法就需要先测量两个链表的长度差，再对齐后同步遍历。这其实引出了另一种常见解法：先算长度差值，让长链表指针先走差值步，然后再两个指针同步走。

第三个追问：如果两个链表都可能有环，这道题会变成什么样？这是一个非常经典的扩展问题。判断带环链表是否相交，需要先找到两个链表的入环点，再做环内外的分段判断。这个难度就完全不是 easy 了，但它的起点正是这道 160 题的基本功。

6.3 从“会写”到“讲清楚”的距离

我发现很多人刷题时有个通病：代码能写出来，但别人问“为什么这样能对”，就支支吾吾说不清楚。这个问题在代码量极少的双指针法上特别明显——正因为代码短，你才更需要把背后的等价路径说清楚。

我建议你花十分钟做一件事：拿一张纸，画两个长度不同的链表，一个长一个短，公共部分画出来。然后手动走一遍双指针的过程，在每个指针上标记它走了多少步、当前指向哪个节点。做完这一遍，你才会真正理解“pA 走过的路径 = A + B 的虚拟拼接路径 = pB 走过的路径”，以后再遇到类似的题，就不慌了。

7. 拓展：从相交链表到更复杂的链表问题

7.1 先求长度差再对齐的替代方案

除了双指针，还有一个思路也很常用：先分别遍历两个链表，计算出它们的长度。然后让较长的链表指针先前进长度差个节点，这样一来，两个指针离链表末尾的距离就相同了。接下来同步遍历，当两个指针指向同一个节点时，就找到了交点。

这个思路的代码量比双指针多一些，但逻辑非常朴素，更容易被初学者接受。它的时间复杂度同样是 O(m+n)，空间复杂度 O(1)。我个人觉得，面试时如果你对双指针的“相遇证明”没有十足把握，可以干脆先讲这个长度差版本，思路清晰，不容易被追问到哑口无言。

7.2 这个套路还能用在哪些题上

双指针“走完自己的路，再去走对方的路”这种思想，在很多链表题里都有变体。找环形链表入环点的快慢指针，用的是“一个跑得快一个跑得慢”的相遇模式；合并两个有序链表，用的是伪头节点加双指针遍历；找两个排序数组的中位数里也有一部分二分思想的影子，虽然数据结构不同，但“对齐两个序列”的思路是相通的。

把这些思路串联起来看，你会发现链表题的解法往往不是靠背，而是靠“状态对齐”四个字：交点问题通过走等长路径对齐，环问题通过速度差对齐，合并问题通过比较大小对齐。理解了这一层，你就不会被某道具体题的标签限制住了。

7.3 本地调试环境的一点建议

刷题时很多环境已经帮你把 ListNode 定义好了，但本地调试的话，你需要自己写。我建议把链表构建、链表打印、链表转数组这几个辅助函数整理成一个公共工具文件，以后所有链表题都能复用。打印函数最好带上节点内存地址的后几位，方便观察共享关系。这算是我自己的一个小习惯，但长期下来确实帮我发现了很多只在复杂用例里才会暴露的引用问题。

最后分享一个我在实际使用中的体会：相交链表这道题，每次刷都会有新的理解。第一次学的时候，我只记住了双指针的代码，觉得自己会了；第二次复习时，我开始追问自己“为什么它能相遇”，把长度差的数学关系画清楚了；第三次带别人讲题时，我才真正注意到那些空链表、单节点、环状扩展的细节。刷题的价值不在于把答案背下来，而在于你愿意为一道 easy 题花多少时间去想它背后的为什么。如果你能把这题讲给一个完全没有思路的人听，让他听懂，那你才算真正吃透了它。