企业官网建设流程全解析

刷链表题的时候，我经常遇到一种尴尬：题面一看就懂，样例一画就明白，可真到写代码的时候，总是在"指针走到哪了""到底该谁先走"这种细节上反复横跳。相交链表这道题就是这样，不同刷题平台对它的编号并不统一，我这边拿到的题单标的是106，英文刷题站上同一道题标的是160，但题目本体完全一致：给定两个单链表的头节点，找出它们相交的起始节点；如果两个链表根本不相交，就返回空指针。

这篇文章我想从最笨的暴力解法讲起，一路说到两种最经典的双指针写法，把每一个解法背后的道理、代码里容易踩的坑、以及面试时真正值得讲的东西都过一遍。不管你是一轮还没刷完的新手，还是马上要面试想快速过高频题的老手，这篇应该都能给你一些可用的东西。

1. 题目到底在问什么：先画清楚Y字型结构

很多同学第一次看到这个题，脑子里想的是"两条链子交叉在一起，像X那样"。这个直觉是错的，而且错得很关键。单链表的每个节点只有一个 next 指针，一旦某个节点被两个链表同时指到，那么这个节点之后的所有路径都只能是同一条了。所以两个相交的单链表，形状一定是Y字型，不可能出现X字型那种"中间交汇又分开"的结构。想明白这一点，后面所有解法都顺理成章。

题目里说的"相交"，指的是内存地址级别的共享，不是节点值相等。两个链表可能各自有一个值为3的节点，但它们是两个不同的对象，后面连接的内容也完全不同；而真正相交的节点，是同一个对象被链表A和链表B同时引用。判断的时候用值相等去比较，等于把这道题做成了"找两个链表中值相等的节点"，那是另一个完全不同的题目。

我们可以用符号把结构描述清楚。假设链表A的独有部分长度为a，链表B的独有部分长度为b，相交之后的公共段长度为c。那么A从头部走到尾，依次经过长度为a的独有段和长度为c的公共段；B同样经过长度为b的独有段和长度为c的公共段。两个链表的差别，完全集中在交点之前的独有长度上，交点之后的所有节点，两个链表是完全共享的。

这个结构还隐藏着一个重要前提：题目默认两个链表内部没有环。如果允许有环，问题会变得复杂很多，那是进阶变种的范畴，我在第六节末尾会专门聊一句。对于无环链表，我们的任务可以简化为：在两条长度可能不同的"前缀"后面，找到第一个共同节点；如果不存在公共段，就返回空。

我自己面试别人时，经常先让候选人在白板上画出这个Y字型结构，然后问一句："如果两个链表相交，从交点到末尾的节点数一定相等，对不对？"很多人能答上来，但真正写代码时还是会漏掉这个条件，这就是对题目本质理解不够深的表现。

2. 暴力解与哈希解：先写出能跑的解法再说优化

碰到链表相交问题，最不动脑子的做法是暴力双重循环：遍历链表A的每个节点，对于每个节点，再去遍历链表B，检查有没有地址相同的节点。

暴力解法用伪代码写出来就是：

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

这个方法能过，但时间复杂度是 O(m×n)，m和n分别是两个链表的长度。如果两个链表都是10万个节点，直接就10亿次比较，在刷题平台上大概率超时。不过它是一个很好的"话头"，面试时先说出暴力解，能让面试官知道你有暴力到优化的完整思路。

2.1 用哈希集合把时间复杂度降到线性

稍微聪明一点的做法是用哈希集合。思路很直白：先把链表A的所有节点地址都放进一个哈希集合，然后遍历链表B，每经过一个节点，就查一下这个节点是不是已经在集合里。第一个命中的节点，就是相交的起点。

原因很简单：如果两个链表相交，那么交点同时存在于链表A和链表B中。当我们把A的所有节点都放进集合之后，B遍历过程中遇到的第一个"已经在集合里"的节点，必然是公共段的起始节点。

def getIntersectionNode(headA, headB): if not headA or not headB: return None 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

这段代码的时间复杂度是O(m+n)，因为两次遍历，加起来走完两个链表；空间复杂度是O(m)，我们需要把链表A的所有节点都存进集合。

用C++写也是同样的逻辑，用 unordered_set 存指针：

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { unordered_set<ListNode*> visited; for (ListNode* cur = headA; cur; cur = cur->next) { visited.insert(cur); } for (ListNode* cur = headB; cur; cur = cur->next) { if (visited.count(cur)) return cur; } return nullptr; }

这里有个值得注意的点：哈希集合里存的是节点指针本身，而不是节点的值。很多语言里对象比较默认比的是引用，Python 的 set 对自定义对象也是先比较哈希再比较地址，所以直接用节点对象没问题。如果存的是值，那又掉回"值相等"的坑里了。

2.2 为什么哈希解在面试里只能算及格

哈希解法本身没有任何错误，而且很多刷题网站上是能 AC 的。但面对"O(m+n)时间 + O(1)空间"的要求，它就不行了。面试官往往会追问一句："你能不能把这题做到常数空间？"

这时候你就要意识到，哈希集合的O(m)空间是为了换取快速查重而付出的代价。具体到这道题，我们并不需要记住A里所有节点，只需要一个办法让两个指针"同时到达交点"。这就是双指针解法的切入点。

3. 长度对齐法：先算长度再同步走，O(1)空间的稳妥路线

既然两个链表从交点到尾部完全共享，那么交点之前的独有长度不同，是导致两个指针没法"齐头并进"的唯一障碍。那最简单的想法就是：先把长度差抹平，让两个指针站在距离链表尾部相同距离的位置，然后同步前进。

这就是长度对齐法，思路非常直白，写起来也不容易出错。

3.1 操作步骤拆解

第一步，数出链表A的长度 lenA 和链表B的长度 lenB。

第二步，如果 lenA > lenB，让指向链表A的指针 pA 先往前走 lenA - lenB 步；反之让 pB 先走 lenB - lenA 步。这样两个指针剩余到各自链尾的距离就一样了。

第三步，pA 和 pB 同步前进，每走一步之前判断一下两个指针指向的节点地址是否相同。第一个地址相同的节点，就是相交的起点。

第四步，如果两个链表不相交，同步走到头之后两个指针都会变成空指针，此时返回空即可。

def getIntersectionNode(headA, headB): def length(head): cur = head cnt = 0 while cur: cnt += 1 cur = cur.next return cnt lenA, lenB = length(headA), length(headB) pA, pB = headA, headB if lenA > lenB: for _ in range(lenA - lenB): pA = pA.next else: for _ in range(lenB - lenA): pB = pB.next while pA is not pB: pA = pA.next if pA else None pB = pB.next if pB else None return pA

注意最后循环结束后的返回值。当 pA 和 pB 都是空指针时，说明两个链表不相交，循环退出，pA 是 None，直接返回 None 是符合预期的；当 pA 和 pB 同时指向交点时，循环退出，返回 pA 就是交点。

3.2 为什么第一次相遇就一定是交点

这个点一定要能解释清楚。抹平长度差之后，pA 和 pB 距离各自链表末尾的距离相同。如果存在交点，那么从当前位置到交点，pA 还需要走"交点之前属于A独有段"的剩余部分，pB 还需要走"交点之前属于B独有段"的剩余部分。这两个剩余部分在长度对齐之后是相等的吗？是的。

更直接地说：在Y字型结构里，如果我们从某个时刻开始，两个指针到公共段起点之前的距离相等，那么它们以相同步长前进，一定会同时踩到公共段的第一个节点。这个"公共段的第一个节点"就是我们要找的相交起点。

3.3 复杂度与适用场景

这个解法的时间复杂度是O(m+n)，因为需要先遍历两个链表求长度，又遍历一次找交点；空间复杂度是O(1)，只用了两个指针变量和一个计数器。

它的优点是逻辑清楚、容易解释、不容易写错；缺点是代码略微有点长，多了一段求长度的逻辑。在实际面试中，如果你一上来写这个解法，面试官通常不会为难你，因为这已经满足"空间O(1)"的硬性要求了。但还有一段代码更短、更漂亮的解法，那就是循环双指针。

4. 循环双指针法：不用算长度，两条路径的步数推导

循环双指针是这道题最出名的解法，网上很多人叫它"浪漫相遇法"。代码短到只有几行，但第一次看的人往往会愣一下：为什么 pA 走完了之后要跳到 headB？为什么这样绕一圈两个指针就一定能相遇？

先看代码：

def getIntersectionNode(headA, headB): if not headA or not headB: return None pA, pB = headA, headB while pA is not pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA

核心逻辑就一个：pA 从 headA 出发，每次走一步，走完了就跳到 headB 接着走；pB 从 headB 出发，每次走一步，走完了就跳到 headA 接着走。直到两个指针指向同一个节点，或者同时为空。

4.1 用数学把原理讲透

设链表A长度为a，链表B长度为b，公共段长度为c。如果两个链表相交，那么pA走到交点的过程是：先把A全部走完，走了a步，此时pA为空；然后跳到headB，再从headB往交点走，还需要 b - c 步，因为交点距离链表B头部有 b - c + 1 个节点。所以pA到交点时总共走了 a + (b - c) 步。

再看pB：先把B全部走完，走了b步，然后跳到headA，再从headA往交点走，还需要 a - c 步。所以pB到交点时总共走了 b + (a - c) 步。

两个数放一起看：a + (b - c) = b + (a - c)，恰好相等。这意味着pA和pB一定会在同一时刻踩到同一个交点。

如果两个链表不相交呢？pA走完A再走完B，一共走了 a + b 步，变成了空；pB走完B再走完A，一共走了 b + a 步，也变成了空。两者同时为空，循环结束，返回的是空指针，完美处理了不相交的情况。

4.2 手动推演一个例子

光看公式可能还是有点抽象，我建议你在纸上画一个具体的链表动手推一遍。

假设链表A是 1 → 2 → 3 → 4 → 5，链表B是 6 → 7 → 8 → 9 → 4 → 5，公共部分是 4 → 5。这里 a = 5，b = 6，c = 2。

按照代码走一遍：

• pA 依次经过 1、2、3、4、5、空，然后跳到 headB 开始走 6、7、8、9、4；
• pB 依次经过 6、7、8、9、4、5、空，然后跳到 headA 开始走 1、2、3、4。

你会发现，pA 跳到 headB 之后走到4，pB 跳到 headA 之后也走到4，两个指针同一时刻停在同一个节点上。这就是循环双指针的相遇过程。

4.3 为什么这个解法会让人觉得"妙但难想"

长度对齐法需要先算长度，相当于我们主动去计算"差多少"。循环双指针的思路不一样，它不计算差值，而是让两个指针各自走完两条链表，用"走路总步数相同"来消除长度差。pA走的路程是"完整A + 部分B"，pB走的路程是"完整B + 部分A"，本质上也是让两个指针走同样多的路程，从而在数学上保证相遇。

这个解法代码最短，但推导过程略绕，很多人能背代码却讲不出为什么。我建议面试前一定要亲手推一遍公式，不然面试官追问"为什么pA要跳过去"时，很容易卡壳。

4.4 循环双指针与长度对齐的本质联系

这两种解法的本质是一样的：都是通过某种方式消除两个链表独有长度的差异。长度对齐法是先算出差值，手动让长链指针先走；循环双指针法是通过"走完自己再接对方"的连续行走，把差值自然吞掉。理解到这一层，你就不会觉得这是两种完全独立的解法了。

5. 把自己当测试机：边界用例与三种典型写错的姿势

这道题代码不长，但踩坑率极高。我见过太多人在很小的细节上翻车，下面把最常见的几种错误和边界情况一次说清楚。

5.1 三种典型错误写法

第一种错误：用值相等判断相交。

# 错误示范 while pA and pB: if pA.val == pB.val: return pA pA = pA.next pB = pB.next

两个链表可能各自有一个值相同的节点，但它们不是同一个节点，后面的路径也不共享。用值判断会把这道题做偏，而且输出结果完全不可靠。

第二种错误：循环里先移动指针再判断。

# 错误示范 while pA and pB: pA = pA.next pB = pB.next if pA is pB: return pA

如果两个链表的头节点就是交点，这种写法会在第一轮循环里直接把指针移到下一个节点，永远找不到交点。正确做法是先判断、后移动，或者把循环条件直接写成 pA is not pB。

第三种错误：判空用 next 是否为空来控制跳转。

# 容易出错的写法 while pA.next and pB.next: ...

这种做法遇到单节点链表非常容易出问题，因为 pA.next 一开始就是空，循环直接跳过，根本不会执行比较逻辑。正确的做法是判断指针本身是否为 None，而不是判断 next。

5.2 边界情况测试清单

本地自测或者面试写完后，可以按下面这张表快速过一遍：

这些用例覆盖了"空链""无交集""交集靠前""交集靠后"最典型的几种形态。代码写完之后，我习惯先跑空链，再跑不相交，最后才跑正常相交，这样能最快暴露边界处理的问题。

5.3 自测的时候怎么构造真正相交的链表

这里有个小坑：刷题平台上，题目输入会给你 skipA 和 skipB 这样的参数来指定相交位置。你本地自测的时候，可不能简单地创建两个值相同的链表，那样构造出来的"交点"根本不是同一个节点地址。

正确的构造方式是先创建链表A，然后在A上选定一个节点作为交点，再创建链表B，把B的尾部接到这个节点上。例如在 Python 里，你可以先建立A的节点，再让B的最后一个节点的 next 指向A的第k个节点。这样构造出来的两个链表才真正共享内存地址，解法才能正确返回结果。

6. 从这道题延伸出去的面试与工程价值

一道题的解法看完了，我更想聊聊它背后折射出来的东西。相交链表为什么是高频面试题？因为它用最小的题面，同时考察了链表结构理解、空间复杂度分析和双指针思维迁移能力。

6.1 面试官真正在观察什么

首先，面试官会看你有没有抓住"相交 = 地址共享"这个核心。很多人一上来就写值比较，这一下就暴露了对链表底层结构理解不到位。其次，空间复杂度意识很重要，从暴力解到哈希解，再到O(1)空间的双指针解，这是一个很完整的优化阶梯，能清楚地展示分析思路。最后，双指针解法的解释是否清晰，能看出你对"相遇问题"有没有真正的理解，而不是只会背模板。

刷题的时候，很多人背下了几个模板，但换一道题就不知道用哪个。相交链表这个例子其实很适合用来建立一种"双指针套路库"：长度差对齐、快慢指针、走完再接对方的循环遍历，这些方法在不同题目里反复出现。

6.2 延伸变种：有环链表与多链表相交

如果面试官想加难度，最常见的变形是：如果链表中有环怎么办？

这里简单说个方向，不做代码展开。有环的相交问题，通常要先找到环入口，然后利用环入口把链表分成"环外部分 + 环部分"，再判断两个链表的公共节点。处理逻辑会从单链表的Y字型问题，升级成混合了链表环检测的问题，复杂度也会上一个台阶。

另外还有多链表相交的变种，比如给了k个链表，要找出所有相交的位置。这类题通常会退化成两两配对 + 并查集一类的思路，已经不是这道题本身能覆盖的范围了，但理解"地址共享"这个本质，能帮你快速找到分析问题的方向。

6.3 工程里"共享后缀"的影子

说到工程应用，相交链表这种"多个引用共享一段结构"的场景，其实在不少地方都能看到影子。比如日志系统里，多条日志链如果有相同的来源前缀，可能会共享某一段不可变节点；再比如内存管理或者对象引用图中，判断两个对象是否最终引用到同一个公共祖先，思路也和这道题神似。

我自己带算法小组时，每次讲这道题都会让伙伴们先在纸上画出Y字型，标出a、b、c三段长度，然后手动推演一遍循环双指针的路线。推完之后，大家普遍对双指针消除长度差的体会深了很多，后面再去做环形链表、找中点的快慢指针题，明显顺手不少。我的建议是，不要停留在背"双指针浪漫相遇"的代码，真的花十分钟把公式推一遍，比你多做十道重复题都有用。