企业官网建设流程全解析

最近在准备算法面试的不少朋友都跟我吐槽，链表题看着简单，一上手就乱。尤其是“相交链表”这道题，LeetCode 第160题，很多人第一次做的时候，要么用暴力解勉强跑通，要么看了题解也似懂非懂，换个写法就懵。这道题特别典型，它考的不是复杂的算法，而是你到底有没有理解链表“指针”的本质——两个链表怎么共享一段节点，以及怎么用最少的额外空间把交点找出来。今天我就把这题的几种思路、推导过程、代码细节和坑全部展开讲一遍，建议先收藏再刷。

这题适合谁看？刷 LeetCode 到了链表章节、准备面试、或者学数据结构想搞明白“引用”和“地址”区别的人。我会把哈希集合解、双指针解，包括长度差法的逻辑一步步拆开，没有基础也能跟着走下来。

1. 题目到底在说什么

先明确一下题面：给定两个单链表的头节点 headA 和 headB，如果它们在某一个节点开始，后面所有节点都相同（注意，是同一个节点对象，不是值相等），就说明两个链表相交了。要求你找到这个相交的起始节点；如果没有交点，返回 null。

很多人第一反应是“两个链表还能相交？”没错，单链表每个节点只有一个 next 指针，所以不存在 Y 型之后又分叉的情况。一旦相交，之后的路就是公共的。这也是为什么这道题能够用数学推导去优化。

再强调一个关键点：题目说的是“引用相同”，不是两个节点里的值相同。比如你有两个不同节点，各自 val 都是 8，但它们在内存里是两份，这不叫相交。这个点我在后面会反复提到，很多报错都出在这。

面试的时候，考官通常还会追问一句话：你能否用 O(1) 额外空间解决？这就排除了哈希表方案，逼你往双指针上想。

2. 哈希集合法：最直白的“记录+查找”思路

2.1 思路与原理

这是我个人觉得最不用动脑子的解法。你遍历链表A，把每一个节点对象放进一个哈希集合（或哈希表）里。然后再遍历链表B，一个一个检查当前节点是不是已经在集合里了。第一个在集合里的节点，就是交点。

为什么用哈希集合而不是数组？因为哈希集合的查找是平均 O(1) 的。你总共要遍历两个链表，各走一遍，所以时间复杂度是 O(m+n)，m 和 n 分别表示两个链表的长度。空间上要存下链表A的所有节点，所以是 O(m)。

2.2 代码模板

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: 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

就这几行，很简单，没什么需要多说的。跑一遍就过了。

不过你要是把这段代码直接甩给面试官，人家大概率不买账。因为这是“解法一”，是最容易想到的，谈不上亮点。面试官想看的是你怎么优化它，怎么从 O(m) 的空间降到 O(1)。而空间上的跨越，靠的就是双指针。

3. 双指针解法：整个题目最核心的思路

3.1 核心推导：为什么两个指针一定会相遇

我先直接给出结论：pA 从 headA 出发，pB 从 headB 出发，两者都一次走一步。pA 走完了链表A就转到 headB 继续走；pB 走完了链表B就转到 headA 继续走。如果两个链表相交，那么它们会在交点相遇；如果没有交点，它们会在 null 处相遇。

这句话很好背，但关键是理解“为什么”。

我们设链表A在交点之前的部分长度为 a，链表B在交点之前的部分长度为 b，公共部分长度为 c。

• 链表A的总长度是 a + c
• 链表B的总长度是 b + c

pA 要走到交点，一共需要走 a + c + b 步（先走完自己 a+c，再转到链表B从头走上 b 步，就到达了交点）。 pB 要走到交点，一共需要走 b + c + a 步（先走完自己 b+c，再转到链表A从头走上 a 步，也到达了交点）。

看这两个数字：a + c + b = b + c + a。完全相等。

也就是说，在 pA 走了 a+c+b 步、pB 走了 b+c+a 步的时候，两只指针站在同一个节点上，这个节点就是交点。它们走的路不一样长，但加起来的总步数一样，最后殊途同归，在同一个节点相遇。

这个理解很重要。你要是只背“走完换路”，不去推导等式，很容易在写循环条件的时候犯迷糊，比如不知道什么时候该换路、什么时候该停止。

3.2 不相交的情况

再看两个链表没有交点的情况。这时公共部分长度 c = 0。

pA 一共走 a + b 步，会从 headA 走到链表B的末尾（null）。 pB 一共走 b + a 步，也会从 headB 走到链表A的末尾（null）。

两个指针走的总步数依旧相等，所以它们会在 null 这个“虚拟节点”处相遇。返回 null 就对了。

这里有个细节值得注意：如果两个链表长度相等且没有交点，那两个指针会在走完各自链表的那一刻同时为 null，直接退出；如果长度不等，需要换路之后才会同时为 null。不管怎样，一定会同步到达 null。原因还是那四个字：总步数相等。

3.3 代码怎么写才算稳

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: pA, pB = headA, headB while pA != pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA

循环条件就一个：pA != pB。这里必须用“节点对象比较”，而不是值比较。只要两个指针不是同一个对象，就继续走。pA 走到 None 也不是结束，而是让它换到 headB 继续。只有一种情况下 pA 和 pB 相等且为 None，那就是两个链表没有交点，循环自然结束，返回 None。

我见过很多人写这个循环的时候，喜欢加一个计数器，担心死循环。实际上不需要。前面推导过，最坏情况下 pA 和 pB 各走 m+n 步，一定会遇到（要么节点相同，要么同为 None）。数学保证不会死循环，代码不用额外保护。

4. 解法对比：不同思路的取舍

4.1 三种常见思路横向对比

除了上面这两种，还有一些人会用“长度差法”做：先分别测出两个链表的长度，算出差值 k，让长的那个链表指针先走 k 步，然后两个指针同步走，碰到的第一个相同节点就是交点。这个解法同样 O(1) 额外空间，但需要两次遍历来求长度，代码比双指针法多一些步骤。

暴力双层循环我就一句话带过：对链表A的每个节点，都去链表B里找一遍有没有相同节点。写起来简单，但 m*n 的复杂度，在长链表上直接超时。刷题可以图快，面试不行。

4.2 为什么双指针法是面试最优解

面试官问这题，不是为了看你写哈希表（虽然这也是一种正解），而是想看你有没有能力从 O(m) 的空间优化到 O(1)。双指针法和长度差法都能做到，但双指针法代码更简洁，不需要预先遍历两次求链表长度，一次循环搞定，思路也更优雅。

实际面试场景中，我推荐你先说哈希集合方案（因为它最好想，说错了也能兜底），然后主动提出“我能优化到 O(1) 空间”，再写出双指针。这样既展示了你基础的扎实，又展示了优化意识，比一上来就甩双指针解更能拿分。

5. 动手验证：构造测试用例

5.1 怎么在本地自己测

LeetCode 网页上跑题很方便，但你要是想本地调试，或者在 IDE 里写完了再贴回去，得自己会构造链表和交点。这是我的个人习惯做法，分享给大家。

先用一个公共尾部，再分别构建链A和链B的独立部分，最后接上公共尾部：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def build_lists(): # 公共部分: 节点值 8 -> 4 -> 5 common = ListNode(8, ListNode(4, ListNode(5))) # 链表A: 4 -> 1 -> 公共部分 headA = ListNode(4, ListNode(1, common)) # 链表B: 5 -> 0 -> 1 -> 公共部分 (注意这个1和A里的1不是同一个节点) headB = ListNode(5, ListNode(0, ListNode(1, common))) return headA, headB, common headA, headB, common = build_lists() s = Solution() result = s.getIntersectionNode(headA, headB) print(result is common) # 期望输出 True

这里我用了一个小技巧：构建公共部分时用一个变量 common 存下来，后面验证的时候直接判断result is common，而不去比较 val。因为 val 完全可能出现重复，比如链表A里独立部分有一个值为 1 的节点，链表B里独立部分也有一个值为 1 的节点，但它们不是同一个对象。

5.2 测一个不相交的用例

def build_non_intersecting(): # 链表A: 1 -> 2 -> 3 headA = ListNode(1, ListNode(2, ListNode(3))) # 链表B: 4 -> 5 headB = ListNode(4, ListNode(5)) return headA, headB headA, headB, _ = build_non_intersecting() # 注意这里没有公共节点 s = Solution() result = s.getIntersectionNode(headA, headB) print(result is None) # 期望输出 True

这个用例特别能验证循环是否会正确退出。如果代码里某处pA = pA.next if pA else headB写成了pA = pA.next，遇到 None 没有换路逻辑，就会直接报AttributeError: 'NoneType' object has no attribute 'next'，或者提前退出返回一个错误的节点。

5.3 边界条件清单

这些边界情况，刷题的时候一定要在草稿纸上手推一遍，别只在脑子里过。我当初就是把“一个空链表”这个 case 漏了，本地测试全绿，一交 LeetCode 就报错，查了半天才发现问题。

6. 常见问题与排查思路

6.1 为什么我的双指针没相遇，反而死循环了

很多人写双指针都会遇到这个困惑，我直接说结论：只要你的换路逻辑正确，不可能死循环。所谓“换路逻辑正确”，就是：

pA = pA.next if pA else headB pB = pB.next if pB else headA

注意是if pA，不是if pA.next。你要判断的是当前节点是否为 None，如果是 None，说明这条路走完了，换到另一条路的头节点；如果不是 None，正常走 next。

如果你写成了pA = pA.next if pA.next else headB，那当 pA 指向最后一个非空节点时，它的 next 是 None，你会提前把 pA 换到 headB，导致步数错乱，最终进入死循环或者错误结果。

还有一个隐蔽的坑：如果你在换路之后，让 pA 和 pB 各走了一轮，但中途把其中一个指向了 None 而不是换路，另一个还在走，那它们就永远不会相等了。比如：

# 错误写法示例 while pA != pB: pA = pA.next # 走到 None 就停了 pB = pB.next if pB else headA # pB 换路了，pA 没换

这种不对称处理是 bug 的主要来源。写双指针的黄金法则是：两个指针的更新逻辑必须完全对称。你在做任何修改之前，先把这行代码摆在一起，眼睛扫一眼是不是一模一样（只是变量名不同）。

6.2 链表的“值相等”不等于“节点相等”

这是我刷题过程中踩过最烦的一个坑。题目要求的是引用相等，但很多人写判断的时候下意识用：

if pA.val == pB.val: return pA

这就错了。两个链表完全可能在不同位置有相同值的节点，但它们不是同一个对象。你返回一个独立节点，LeetCode 判断result == expected时比较的是节点对象，直接就判定错误了。

正确做法就是比较节点本身，不要碰 val。while pA != pB已经是对象比较了。如果你非要去拿 val 比较，那必须在确认pA is pB之后才能谈 val。

6.3 怎么快速定位“输出一个错误节点”的问题

如果你的双指针解法最后返回了一个节点，但不是题目要求的交点，大概率是换路时机错了。我常用的排查方法是：在循环里加一个step计数器，每走一步加一，输出每个 step 对应的 pA.val 和 pB.val。然后手动对照推导的步数表：

• 链表A: 4 -> 1 -> 8 -> 4 -> 5
• 链表B: 5 -> 0 -> 1 -> 8 -> 4 -> 5

pA 的路径是：4,1,8,4,5, 然后换到 5,0,1,8，在第9步到达交点 8。 pB 的路径是：5,0,1,8,4,5, 然后换到 4,1,8，在第8步到达交点 8。

注意两者到达交点时的步数不一样，但最终会碰头。如果你在输出中看到 pA 和 pB 同时为某一对“值相同但节点不同”的值，那就是误判了。这时候你要检查的是：是不是把某个节点的 val 和另一个节点的 val 相等当成了相交条件。

6.4 关于“最新版”题目的一个坑

LeetCode 现在的链表定义里，节点从ListNode变成了可选的Optional[ListNode]。在一些早期题解里，你会看到def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode，但新版本里 Python 的类型注解推荐写Optional[ListNode]。有的环境对类型不敏感，能跑，但提交到某些严格检查的 OJ 上可能报错。建议直接统一用：

from typing import Optional class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:

另外，现在有些题解里用的是while pA != pB:的写法，有一些则用while pA and pB:加一个标志位的写法。我个人只推荐前者，因为它简洁且数学上严密。后者引入额外变量，逻辑分支更多，更容易出错。

7. 从这道题延伸出去：双指针思维的通用性

7.1 环检测里的双指针

相交链表这题的核心思维其实和另一道经典的“环形链表”题共用同一个底层逻辑：双指针。环形链表用的是快慢指针，快指针一次走两步，慢指针一次走一步，如果有环，两者一定会在环内相遇。相交链表则是两个速度相同的指针，通过“延长步数”制造必然相遇的条件。两者都依赖一个关键思想：用步数上的补偿，抹平初始位置的不平等。

理解了相交链表的“总步数相等”推导，你再看环形链表的 Floyd 判圈算法，就会觉得特别顺。它们不是孤立的题目，而是同一套思维的两个场景。

7.2 现实工程中的应用场景

说了半天解题，这题在真实工程里到底有什么用？最典型的就是找两个日志链路或者服务调用链的公共祖先节点。比如你排查一次分布式请求，发现有两个 trace 片段，它们的前半段各自独立，后半段汇聚到同一个服务。用相交链表的双指针思路，可以快速找到那个汇聚点，帮你定位源头。

另一个场景是内存检测里的共享内存块查找。系统里两个进程各自维护一条内存引用链，如果发现它们指向了同一块公共内存，可能是内存泄漏或者共用缓存。这种场景的底层结构和相交链表完全一致。

我自己在做某个模拟项目X（一个跨平台系统的若干服务模块）的时候，就曾经把这段双指针逻辑抽象成了一个公共函数，专门用来在配置依赖图里找两条配置链的公共依赖项。改动很小，但带来了很直观的收益——原来需要两层循环扫描，换成双指针一次遍历就搞定了。

7.3 面试进阶：你能讲清楚“为啥这样能相遇”吗

刷题的人很多，能把代码写对的人也很多，但面试官想要的解释其实是这个：

两个指针最终都会走完“属于自己的路 + 对方的路”，相当于总路程相等。在路程相等的前提下，如果存在交点，它们在到达交点时满足一个镜像关系——A指针走到了 B 的前半段，B指针走到了 A 的前半段，两个“前半段”加起来正好跨过了交点。因此它们一定在交点相遇。

如果你能把这个话说出来，而不是背一句“走完换路”，面试官基本就认可你确实理解了。我在模拟面试中见过很多候选人，代码秒写，但问他“为什么一定能相遇”，支支吾吾。这就是典型的背题，而不是会题。

我个人的建议是：做这道题的时候，不要急于看答案，先在纸上画两个相交的链表，把 pA 和 pB 的每一步标出来，走一遍。画完了，再去看代码，你的理解会完全不一样。

8. 实操心得：我是怎么从“背题”到“会题”的

最后聊点我自己刷这题的经历。第一次遇到相交链表，我完全没思路，直接看题解，背会了双指针写法。一周后再做，写出来一样，但面试模拟时被问到“为什么最后一定相遇”，我愣住了。因为我只记住了代码，没记住推导。然后我花了大概一小时，自己在纸上把各种情况都画了一遍，才彻底开窍。

后来我再刷类似的题，都坚持做三件事：

第一，不看题解先自己想。哪怕想出来的解法是 O(m*n) 的暴力，也没关系，起码你的脑子启动了。想不出最优解没关系，想出的暴力解就是你的基线，后面优化才有方向。

第二，手推一遍数学公式。就像本文里 a+c+b = b+c+a 这种推导，看起来简单，但只有自己写一遍，才能内化成直觉。遇到下一道类似的题，你会条件反射地去找“什么量是相等的”。

第三，故意写一遍错误代码。我有时候会特意把换路条件改成if pA.next is None，然后跑一遍，观察它怎么崩、怎么错。这个过程能让我牢牢记住正确条件为什么正确。

这三步走完，这题才算真正属于你了。

如果你准备面试，建议再想想这些变体：如果链表可能有环怎么办？如果要求返回相交的第一个节点，而不只是判断是否相交，双指针还成立吗？如果两个链表各自独立部分特别长，双指针最坏要走多少步？想清楚这些问题，你的水平已经超过了绝大多数只刷过一遍题的候选人。

反正我现在再看这道题，觉得它就是链表双指针思想的一个完美缩影。代码越短，背后的数学越硬核，这是链表题最迷人的地方。