企业官网建设流程全解析

刷到 Hot100 第 18 题，160. 相交链表。说实话，这道题在链表专题里属于“看起来简单、做起来容易绕”的典型代表。我最早在面试里遇到这题时，第一反应是两层循环暴力判断，被面试官追问了一句“能不能 O(1) 空间”之后，整个人就开始慌了。后来自己把两种主流解法、数学原理和边界条件都梳理了一遍，才觉得这题是真的值得好好写一篇复盘。

这篇文章适合正在刷 LeetCode Hot100 的读者，也适合准备面试想系统过一遍链表题的人。我会把题意、哈希表方案、双指针方案、长度对齐法、常见踩坑点以及延伸变体一次讲透，争取让不同基础的读者都能跟着完整的思路把这道题彻底拿下。

1. 题目到底在问什么

1.1 什么是真正的“相交”

题目给两个单链表的头节点 headA 和 headB，要你返回它们相交的第一个节点；如果没有相交，返回 null。

这里的“相交”指的是节点层面的重合，不是值相等。两个链表从某个节点开始，后面的所有节点都指向同一批节点，形成一个大写的 Y 字形结构。比如链表 A 是 A1 -> A2 -> C1 -> C2 -> C3，链表 B 是 B1 -> B2 -> B3 -> C1 -> C2 -> C3，那么 C1 就是我们要找的相交节点。

为什么一定是 Y 型而不是 X 型？因为单链表每个节点只有一个 next 指针。一旦两个链表在某个节点合并，它们后面走过的路径就必须完全一致，不可能出现先相交、再分开、再相交的情况。X 型结构意味着某个节点有两个 next，这在单链表里不成立。

很多第一次写这道题的人会把“值相等”当成“节点相等”，结果一跑测试用例就出问题。LeetCode 里的链表节点值是可以重复的，比如 A 链表里有节点值 3，B 链表里也有节点值 3，但它们是两个不同的节点对象，只是恰好值相同。判断相交必须比较节点本身，在 Java/C++ 里比较对象引用，在 Python 里比较对象身份，而不是比较 val。

1.2 题目里容易被忽略的两个约束

第一，题目明确说给定的两个链表不会构成环。这个约束很重要，它保证了很多“走到头再从另一条链表开头继续走”的思路是安全的。如果链表可能带环，情况会复杂很多，后面我在延伸部分会专门聊。

第二，函数需要保持原始链表结构不变，也就是不能在解题过程中修改节点的 next 指针。这个约束排除了“把 A 的尾巴接到 B 上再找环”这种取巧做法，老老实实用路径遍历或者数学技巧去做。

2. 暴力方案：哈希表法及其价值

2.1 思路与实现

最直觉的做法是：先把链表 A 的所有节点放进哈希集合，然后遍历链表 B，每到一个节点就检查这个节点是否已经在集合里。如果存在，说明这个节点就是交点；如果遍历完 B 都没有命中，说明两个链表不相交，返回 null。

这个方案的时间复杂度是 O(m+n)，空间复杂度是 O(m)，其中 m 是链表 A 的长度。代码写起来非常干净：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> seen = new HashSet<>(); ListNode p = headA; while (p != null) { seen.add(p); p = p.next; } p = headB; while (p != null) { if (seen.contains(p)) { return p; } p = p.next; } return null; }

Python 版本思路一模一样：

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

2.2 为什么这个方案仍然值得写

哈希表法不是最优解，但它是面试里很好的“起点答案”。原因有三个：

第一，正确性一目了然。把 A 的所有节点记下来，再在 B 里逐个查，逻辑没有任何弯弯绕，不容易写错。

第二，它能作为后面双指针解法的验证基准。我平时刷题如果先写出暴力解，会用它跟优化方案的结果对拍，确认优化算法没有跑偏。

第三，面试官听到这个方案后，通常会顺着问“空间能不能优化到 O(1)”，这就自然地把话头引到了双指针和长度对齐法上。你在面试中先给出能跑的方案，再逐步优化，这才是正常的思考过程，而不是直接背一个双指针答案出来。

当然，哈希表方案不能作为最终的满意答案，因为空间复杂度偏高。链表很长的时候，哈希集合会占不少内存。接下来才是这道题真正精彩的部分。

3. 双指针解法：为什么两个指针一定会相遇

3.1 核心思想

两个指针 pA、pB 分别从 headA、headB 出发，同步往下走。当 pA 走完链表 A，就把它重置到 headB；当 pB 走完链表 B，就把它重置到 headA。继续走，直到 pA 和 pB 指向同一个节点。

这个节点可能是真正的相交节点，也可能是 null，两种情况都表示算法结束了。

代码极短：

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; }

Python 版本：

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

3.2 数学证明：为什么它们会在交点相遇

假设链表 A 不相交部分的长度为 a，链表 B 不相交部分的长度为 b，公共部分的长度为 c。也就是说，链表 A 总长是 a+c，链表 B 总长是 b+c。

pA 从 headA 出发，走完自己的链之后继续走 B 的前半段。当 pA 第一次走到交点时，它走过的距离是 a + c。随后它会走完公共部分，再走完 B 的不相交部分，到达 B 的末尾，这时候走过的距离是 a + c + b。

pB 从 headB 出发，对应的，它第一次到达交点时走过的距离是 b + c。随后它走完公共部分，再走完 A 的不相交部分，到达 A 的末尾，走过的距离是 b + c + a。

a + c + b 和 b + c + a 是相等的。所以在第二轮行走中，当 pA 走了 a+c+b 步、pB 走了 b+c+a 步的时候，它们都站在同一个位置，这个位置刚好就是公共部分的起点，也就是交点。

如果两个链表不相交，可以理解为 c = 0。pA 走过的距离是 a+b，pB 走过的距离是 b+a，最终它们同时走到链表的末尾，也就是 null。while 循环的判断条件是 pA != pB，两个指针同时变成 null 时，条件不成立，循环结束，返回 null。

这里有个非常微妙的点：指针在处理“走完一条链表后换到另一条链表开头”这一动作时，不能只做一次。因为长度差可能很大，一个指针需要等另一个指针走完它的链表才能进入第二轮。这个“互相抵消长度差”的过程，正好是双指针解法的灵魂。

3.3 用一个小例子把流程跑通

假设链表 A 是 1 -> 2 -> 3 -> 4 -> 5，链表 B 是 9 -> 3 -> 4 -> 5，交点是节点 3。

手动模拟一下：

这个模拟表有点长，但它很直观地展示了两个指针是如何通过“换头”操作把长度差抹平的。实际代码里，pA 走完 A 后换到 B 的开头，pB 走完 B 后换到 A 的开头，两者在第二轮后半段会逐渐对齐。

3.4 写双指针代码最容易犯的错

这里我必须强调一个容易翻车的细节：重置指针的操作必须放在 while 循环内部，并且在 pA 为 null 时才重置，而不是用 if 判断一次就完事。

有人会写成这样：

while (pA != pB) { if (pA.next == null) { pA = headB; } else { pA = pA.next; } // 同理 pB }

这个写法问题很大：当一个指针走到最后一个节点时，它确实可以换到另一条链表，但换过去之后它还需要继续往前走，而另一个指针可能还没走完自己的链表。如果你只在“next 为空”时换一次，两个指针的第二轮不同步，可能导致永远遇不到。

正确做法是每走一步都判断当前节点是否为 null，如果是 null 就换成另一条链表的头，否则继续走 next。这样两个指针每轮都恰好走一步，不会因为换链而额外付出步数。

4. 长度对齐法：另一种必修思路

4.1 思路与代码

比双指针更容易向别人解释清楚的方法是长度对齐法。

先遍历 A 和 B，分别求出长度 lenA 和 lenB。假设 A 更长，就让 pA 先走 lenA - lenB 步，然后 pA 和 pB 同步前进，第一个相同的节点就是交点。

为什么有效？因为两个链表的公共部分长度相同，差异只在前缀部分。把较长链表的前缀多走掉一段之后，两个指针就同时到达距离交点相同的距离。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = length(headA); int lenB = length(headB); ListNode pA = headA; ListNode pB = headB; while (lenA > lenB) { pA = pA.next; lenA--; } while (lenB > lenA) { pB = pB.next; lenB--; } while (pA != pB) { pA = pA.next; pB = pB.next; } return pA; } private int length(ListNode head) { int len = 0; while (head != null) { len++; head = head.next; } return len; }

4.2 一个可以顺手做的优化

在计算长度的过程中，可以顺便记录两个链表的尾节点。如果两个尾节点不是同一个节点，那么两个链表必定不相交，可以直接返回 null，省掉后续的指针移动。

这个优化判断相交非常快，尤其适合那种两个链表都很长、但明显不相交的场景。注意它只能作为前置判断，不能代替后续逻辑，因为即使尾节点相同也需要找到交点本身。

4.3 三种方法放在一起比较

面试时我个人推荐先讲长度对齐法作为 O(1) 空间的方案，因为它每一步的理由都很直白：先算长度、再消差值、最后同步走。面试官容易跟上你的思路。

双指针解法代码更短，但在你讲清楚“为什么两个指针会相遇”之前，面试官可能有点懵。你可以把两种都写一遍，显得你对这道题理解足够深。

5. 实战场：常见错误与调试经验

5.1 最典型的死循环场景

我在本地练习时，试过把重置逻辑写成这样：

while (pA != pB) { if (pA == null) { pA = headB; } else { pA = pA.next; } if (pB == null) { pB = headA; } else { pB = pB.next; } }

看起来和正确写法差不多，但有一个陷阱在“一个指针为 null”的时候。

假设 pA 先到了 null，被重置为 headB。而 pB 还没到 null，继续走。下一轮循环，pA 可能还在走 B 链表的前半段，pB 继续走自己的链表。这个时候两者路径并不是简单地相互换路，而是每轮都在同步移动，逻辑上其实是正确的。

真正的死循环往往出现在另一种写法：有人把 pA 重置放到 while 外面，或者只对其中一个指针做重置操作。比如：

while (pA != null && pB != null) { // 找交点 pA = pA.next; pB = pB.next; }

这种写法在两个链表长度不同且不相交时，循环会在某个指针先到达 null 后退出，虽然不会死循环，但会漏掉正确的交点。更隐蔽的问题是如果两个链表相交，较长链表的前缀节点可能永远无法与另一条链表的路径对齐。

为了避免这种问题，我调试时会把循环条件固定写成 pA != pB，并且确保每一轮循环中两个指针都“要么往前走一步、要么重置到另一条链表的头”。这个口诀我背得很熟。

5.2 空指针和边界用例清单

代码写出来能跑，不代表边界用例没问题。我刷这道题必测以下几组：

• 两个链表都为空，返回 null
• 其中一个链表为空，返回 null
• 两个链表只有一个节点且相交，返回该节点
• 两个链表只有一个节点且不相交，返回 null
• 两个链表长度相同，相交点就在开头附近
• 两个链表长度相差很大，比如 A 有 1000 个节点，B 只有 1 个节点且相交
• 节点值重复，但相交点在值相同的节点后面

特别提醒：节点值重复是最容易误导人的测试点。你在本地构造用例时，故意让 A 和 B 的前缀里出现相同的值，但相交点却在更后面的位置，看看你的代码会不会因为“值相等”就提前返回。

5.3 本地调试技巧

LeetCode 的链表输入是用数组表示的，但本地调试时手动构造链表比较麻烦。我常用的做法是写一个辅助函数：

def build_linked_list(values): dummy = ListNode(0) cur = dummy for v in values: cur.next = ListNode(v) cur = cur.next return dummy.next

构造相交链表时，先创建公共部分，再分别接上两个前缀。比如公共部分节点是 c1 -> c2 -> c3，A 前缀是 1 -> 2，B 前缀是 9，那么 headA 就是 1 -> 2 -> c1，headB 就是 9 -> c1。

调试双指针时，打印每一步 pA 和 pB 的地址很有用。Python 里可以打印 id(pA)，Java 里可以打印 pA 的 hashCode。我在模拟时发现两指针在“第二轮”相遇的过程非常直观，打印地址能帮你确认是不是因为重置时机不对导致永远相等不了。

6. 延伸与变体：一道题带出整个链表相交家族

6.1 变体一：只判断两个链表是否相交，不找交点

如果只是判断是否相交，最简单的做法是分别遍历到两个链表的尾节点，然后比较尾节点是不是同一个节点。因为相交链表的尾节点必然是同一个。

这个思路在长度对齐法里可以作为前置优化，在面试中也可以单独出现。它把问题简化成“O(1) 空间下的尾节点比对”，比求交点更容易解释。

6.2 变体二：链表可能带环呢？难度完全不一样

如果题目去掉“无环”这个约束，情况会变得非常复杂。需要先判断两个链表各自是否带环，找环入口，然后分三种情况：

• 两个链表都不带环，走普通相交逻辑
• 一个带环一个不带环，不可能相交，直接返回 null
• 两个都带环，可能不相交，也可能相交点在环外或环内

处理“相交点在环内”时，返回哪个节点都可以作为交点，因为环内任意节点都可以看作相交点。这需要结合快慢指针找环入口、判环等知识，已经不是一道简单题了。

我刷 Hot100 时先掌握无环版本，再单独刷“环形链表 II”补充带环找入口的方法，这样循序渐进比较舒服。

6.3 这道题和同专题题目的串联复习

链表家族的题非常适合集中刷：反转链表、链表中倒数第 k 个节点、合并两个有序链表、环形链表、删除链表倒数第 N 个节点、回文链表等。它们共同的基础操作就是遍历和指针移动，很多题目互相之间能复用思路。

160 题的核心价值在于“长度差消除”这个思想。这个思想也能迁移到数组、字符串的问题中，比如找两个有序数组的公共后缀等场景。刷题的时候把一个思路拓展到多种题型，比机械地刷十道题更有收获。

我在网上看题解时经常看到有人把这道题和“LeetCode 周赛 430”、“073 爱吃香蕉的狒狒”这类题放在一起对比，其实共同点是：题目描述都挺生活化，但真正解决时要先抽象出数学关系。160 题的数学关系是 a+c+b = b+c+a，073 的数学关系是二分枚举吃香蕉速度。用这种视角刷题，你会慢慢发现不同题目之间的手感是互通的。

7. 刷题之外，我还想多说两句

这道题我前前后后写了不下五遍，每次重写都能发现新的理解角度。第一遍会背答案，第二遍开始心里模拟指针的移动，第三遍才真正理解为什么第二轮一定能相遇，到第四遍我甚至能不用代码、只用口头给面试官讲清楚整个过程。

我自己沉淀下来的一个经验是：链表题别急着看题解，先在纸上画图。把两条链表画出来，标出交点，然后用手指头模拟两个指针的移动，走完一遍你自然就会写了。画图这一步能规避掉 80% 的“看懂了但写不出来”问题。

推荐大家把这道题放进自己的“必须手写两遍以上”清单。第一遍照着思路写，第二遍合上题解默写，第三遍尝试给旁边的人讲解。能做到把 a+c+b 和 b+c+a 这个等式脱口而出的时候，这道题才算真正拿下了。