企业官网建设流程全解析

1. 题目到底在问什么：为什么easy模式下藏着最经典的链表思路

LeetCode 热题100里的第160题相交链表，我在好几个技术社群里都看到有人把它列成“看题解秒懂，自己动手永远差一口气”的典型。题目标注的是easy模式，但它考察的东西一点都不浅：节点引用的理解、指针操作、边界处理，还有一条非常经典的“双指针交换路线”思路。我很建议正在准备算法面试的人把它当成链表入门的第一道深挖题，而不是简单记一下答案就划走。

1.1 把题目翻译成人话

给你两个单链表，它俩可能在某一个节点之后完全重合，也可能是两条平行线，从头到尾没有任何交集。要求你写一个函数，找到它们开始相交的那个节点。如果压根不相交，就返回空指针。

题目里最关键的一个词是“相交”。链表是节点通过指针串起来的结构，所以这里的相交并不是指两个节点的值相等，而是指同一个节点对象同时出现在两条链里。这是最初级的理解门槛。很多人在纸上画图时觉得两条链“叉”在一起，实际上链表相交之后不是X形，而是Y形：两条链从各自的头出发，在某一点汇合，之后共用同一条尾巴。

约束条件大家应该都看过：时间复杂度要求O(m+n)、空间复杂度要求O(1)。也就是说你最多只能把两条链完整扫一遍，而且不能用哈希表这类额外容器。这个限制基本排除了“把A链所有节点存起来，再遍历B逐个查”的写法，逼着你从指针本身想办法。

1.2 为什么很多人“秒懂又写不出”

我见过不少刷题笔记里把解法写成一段很短的双指针代码，读者看完觉得“就这？”，结果合上屏幕自己一写就出错。问题通常出在三个地方。

第一，不理解指针为什么要在走到链表尽头时跳到另一条链的表头。如果只是背代码，很容易写成“走到头就停止”，那两条指针永远只会各自走完自己那条链，长度不一样就根本碰不到。

第二，没想明白“空指针切换”的具体时机。细枝末节决定了能不能通过边界用例。比如两条链表不相交时，最终两个指针会同时变成空指针，这个状态本身就是“不相交”的返回条件。

第三，完全忽略了空链表的输入。我见过好几个人的版本，先声明“if not headA or not headB: return None”，但有人把这条判断放在循环外，有人放在循环内，两头的逻辑其实不一样。

这题的easy模式其实有迷惑性，代码量少不代表好写对。它考察的是你能不能把一个数学上“必然相遇”的结论，翻译成不会死循环、不会空指针异常的代码。

1.3 面试官拿这题考什么

如果在面试里碰到这道题，对方大概率不是想看你背出双指针，而是想看你怎么推演。我后来复盘过几次模拟面试，觉得这题的考察点依次是：

• 能不能准确说出“相交”在链表里是指引用相同，而不是值相同；
• 能不能自己在白板上推导出“路程相等则必然相遇”的结论；
• 写出来的循环在无相交场景下是否稳定终止；
• 有没有处理空链表。

原题虽然是easy模式，但包含的这些点足以区分“背过题”和“真懂链表”两类候选人。

2. 双指针相遇的数学原理：路程相等才是核心

我当时第一次看双指针解法时，脑子里冒出来的问题是：凭什么两个指针交换着走就一定能遇得上？后来我把路径画出来才算真正想通。理解这个原理，比记住代码重要得多。

2.1 两条路线合起来是同样的一段全程

假设链表A在相交点之前的长度为a，链表B在相交点之前的长度为b，公共部分长度为c。两个指针P1和P2分别从A、B的表头出发，速度完全一样。

P1的路线是：先把A整条走完，长度a+c；然后跳到B的表头，继续走B上属于自己的那段，直到相交点，这一段长度是b。所以P1从出发到相遇共走了a+c+b。

P2的路线是：先把B整条走完，长度b+c；然后跳到A的表头，继续走A上属于自己的那段，直到相交点，这一段长度是a。所以P2从出发到相遇共走了b+c+a。

两个路程完全相等，都是a+b+c。既然速度相同、路程相同，从同一时刻出发，就一定会在同一时刻到达同一个位置。而它们在到达相交点之前，各自走过的“前段”里完全没有共同节点，所以它们唯一可能相遇的位置就是那个公共部分的起点。

这段推导是整个算法的心脏。用大白话总结就是：我把自己没走过的路补给你，你把自己没走过的路补给我，两个人的总路程打成平手，自然在同一点碰头。

2.2 举个具体例子走一遍

光看公式还是有点抽象，我习惯用具体数字推演。

假设A链从表头到相交点有2个节点，B链从表头到相交点有3个节点，公共部分有2个节点。那么a=2、b=3、c=2。

P1从A头出发，走完A的4个节点后站在A链的末尾尾节点上，下一步跳到B的表头，此时它已经走了4步。P2从B头出发，走完B的5个节点后站在B链的末尾尾节点上，下一步跳到A的表头，此时它已经走了5步。

接下来继续走：P1在B链上还需要走3步才能到达相交点（也就是b=3）；P2在A链上还需要走2步才能到达相交点（也就是a=2）。由于P1目前比P2少走1步，而终点相同，所以P2会比P1早1步到达相交点吗？不对。注意P2虽然先到相交点，但它不会停下来，如果题目有环它可能还会继续走下去？但这题没有环。一般情况下代码循环的条件是“两个指针不相等就继续走”，所以P2到了相交点之后如果P1还没到，P2会继续往公共部分深处走，直到P1也到相交点，两者在公共部分内的某个位置碰面。

这里就暴露了一个问题：如果P2先到相交点并继续往前走，那它和P1相遇的位置就不是相交点了，而是公共部分里的某个更深的节点。这好像和上面“P1、P2必然在相交点相遇”的结论矛盾？其实不矛盾。我上面推演时漏了一个关键细节：真正的双指针写法里，两个指针不是“到达相交点就停”，而是继续走直到相等，而这个“相等”发生的位置必须是相交点。需要重新仔细地走一遍。

重新走：P1到A尾时走了a+c=4步。然后跳到B头，走B的节点。P2到B尾时走了b+c=5步。然后跳到A头，走A的节点。P2跳过去之后在A链上已经走了0步，位于A头，继续走。P1在B链上也走了0步，位于B头。此后P1每走一步，P2也走一步。P1在B链走到相交点需要b=3步；P2在A链走到相交点需要a=2步。所以当P2走了2步到达相交点时，P1在B链上才走了2步，离B链的相交点还差1步。此时P2继续前进到公共部分的第2个节点，P1继续前进到B链的相交点，也就是公共部分的第1个节点。两者还不相等。P2再走一步到公共部分的第3个节点（如果公共部分只有2个节点，那下一步就出链表了，跳到B？不对，要按路线来）……

这里我意识到之前的等量关系需要在程序语义下重新理解。上面2.1说的“P1共走a+c+b到达相交点”和“P2共走b+c+a到达相交点”确实成立，但在时间轴上，P2会先完成“自己链+对方链”中的前一段，到达相交点；而P1还在路上。因为两者不是同时到达相交点，所以“相遇于相交点”需要另外的论证。

真正严谨的论证方式应该是：两者最终都会走a+b+c步；在这a+b+c步中，只有最后c步（公共部分）两者走过的节点是同一个集合；因为速度相同，当走过a+b步时，两者同时进入公共部分；再走c步，同时离开公共部分。那么在进入公共部分的那一刻，两者是否在同一个节点？不一定。进入公共部分时，P1从B链进入公共部分，所在位置是公共部分的起点；P2从A链进入公共部分，所在位置也是公共部分的起点。不对，P2从A链尾再走一步就进入公共部分，但A链的“对方链前段”长度是a，走完a之后P2接着走A链的公共部分，从公共部分起点开始。P1同样，走完B链的前段b之后进入公共部分。所以两者是同时进入公共部分，且都是从公共部分起点进入的。关键在于：它们进入公共部分之前都先走完了“对方链的非公共部分”，而这段路程长度分别是b和a，两者在时间和空间上不一定对齐，但由于总路程相同，它们到达“进入公共部分”这个事件的时间点相同？要计算：P1到达“公共部分起点”的时间是“走完A的a+c步+走完B的b步”，即a+c+b。P2到达“公共部分起点”的时间是“走完B的b+c步+走完A的a步”，即b+c+a。两者相同。所以它们确实在同一时刻进入公共部分，且都是公共部分的起点。因此相遇点就是公共部分的起点，即相交点。前面的时间差推演为何错？我错在把P2到达“A链上的相交点”的时间（b+c+a=5+2=7）和P1到达“B链上的相交点”的时间（a+c+b=4+3=7）看成不同，其实都是7步。P2先到达的是A链的相交点，但那个时刻P1也同时到达B链的相交点，两者距离相同位置相同，所以碰面。我上面推演里的“P2走2步到达A链相交点时P1才走2步”是把起点对齐搞错了。具体以a=2、b=3、c=2为例，P1总路线：A头→A1→A2→公共1→公共2（走完A），跳B头→B1→B2→B3→公共1。这个“公共1”是B侧入口，也是P2从A侧进入的同一个“公共1”。P2总路线：B头→B1→B2→B3→公共1→公共2（走完B），跳A头→A1→A2→公共1。P1走到“公共1”时共走了a+c+b=2+2+3=7步；P2走到“公共1”时共走了b+c+a=3+2+2=7步。速度相同，所以同时到达。上面的错误推演是让P2在A链上走2步到公共1时，错误地把P1在B链上走的2步当作起点相同，实际上P1已经先走完了A整条链和B的前2个节点，位置在B3，差一步到公共1；而P2走A1、A2后到达公共1。等等，再算一遍：第6步结束时，P1在B3，P2在A2。第7步，P1走B链的下一节点即公共1，P2走A链的下一节点也即公共1。两者第7步同时到达公共1。所以并没有“早一步”，因为两者第7步落点相同。我之前说“P2到A链相交点需要2步”是从“跳到A头之后”数，但P1跳B头之后也需要3步；两者跳到对方链头的时间不同，但总步数相同，落点相同。这就是为什么说，双指针一次循环内就能相遇，而不是靠提前停在相交点。

2.3 为什么能保证不错过，也不会死循环

两个指针速度完全一致，而且每一步都同步推进。因此它们不会出现“一个已经穿过交点，另一个还差一点”的错位。原因在于它们进入公共部分的时刻完全一致，而公共部分是从同一个节点开始的——也就是说它们同时踏进同一个节点，自然就是相交点。

如果两条链没有交点，相当于c=0。那么P1走a+b，P2走b+a，同时走完所有节点，最后同时变成空指针。循环里判断“两个指针不相等就继续”，此时两者都为空，循环结束，返回空指针即可。所以无交点时也不需要额外标志位，天然会终止。

这个“路程补足”的思路是整道题最漂亮的地方。理解了这一点，代码就只是一层窗户纸。

3. 可运行代码与逐行拆解

原理讲清楚之后，代码实现就变得顺理成章。我用Python写一版最简洁的双指针解法，然后逐行说明每个细节。这版代码可以直接跑通LeetCode原题，也可以搬到本地做测试。

3.1 Python双指针实现

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: if headA is None or headB is None: return None pA, pB = headA, headB while pA is not pB: pA = pA.next if pA is not None else headB pB = pB.next if pB is not None else headA return pA

这段代码一共不到十行，但每一行都有讲究。if headA is None or headB is None是提前处理空链表的快捷返回。实际上就算不写这行，后面的循环也能在特定条件下正确终止，但写了它会让逻辑更清晰，也减少无谓的循环。

3.2 几个关键细节

第一，循环条件是pA is not pB。这里用的是is not而不是!=，因为链表节点对象比较的是身份而不是值。==会去调用对象的值比较，两个节点即使值一样也不是同一个节点，容易误判；而is not只比较引用地址，正好符合题目要求。“相交”就是引用相同，遇到同一个对象才停下。

第二，指针走到None时切换链表的写法。我见过有人写成：

if pA.next is None: pA = headB else: pA = pA.next

这个写法看起来很自然，但它有个隐患：pA走到最后一个有效节点时，会先跳到headB，而没走到null就切换，意味着“走完整条链”的完整路线变成“走到最后一个节点就切”，而不是“走到null才切”。对于某些链表，这样也能得出正确答案，但会让路径长度和上面推导的不一致，容易在特殊长度组合下出错。更稳的是pA = pA.next if pA is not None else headB这种“先走到null再切换”的写法。

第三，无交点场景的终止。两条链都不为空但没有交点时，pA和pB会在各自走完A+B和B+A所有节点后同时变成None。循环条件判断None is not None为假，退出循环，返回的pA是None。不需要额外设置“是否相交”的布尔变量，这个设计非常干净。

3.3 哈希集合版本：用空间换直观

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> 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)的要求，但作为对照理解起来非常直观：先把A链所有节点引用存进集合，再遍历B链，第一个命中集合的节点就是相交点。用哈希集合而不是列表，是因为集合的查找是O(1)，整体能压到O(m+n)。这个版本适合在本地做交叉验证，用来确认双指针版本的结果是否正确。

4. 边界条件与高频易错点：这些坑90%的人都踩过

代码虽短，我每次给同学讲这道题时都能从他们的错误版本里挑出几种典型问题。这里集中整理一下，防止你写完代码在本地自测通过、一提交却报错。

4.1 空链表和单节点链表

如果headA或headB本身就是空，直接返回None，这个大家基本不会忘。容易翻车的是单节点链表加上“相交点在头节点”的组合。

假设两条链都是只有一个节点，而且这个节点是同一个对象。按照双指针逻辑，pA和pB都指向同一个节点，while循环一次都不执行，直接返回该节点，正确。

如果两条链都只有一个节点且不是同一个对象，那么pA和pB不相等，进入循环。第一步都走到None，然后切换到对方的头节点；第二步pA变成headB的节点，pB变成headA的节点，节点不同继续走；第三步都从对方头节点的next走到None，双双退出循环返回None。正确。

4.2 值相等不等于节点相等

这是新手最容易踩的坑。两个节点的val都是3，但它们是两个独立对象，只是数值碰巧一样。如果用pA.val == pB.val作为相遇条件，代码可能在错误的位置提前返回。

举个例子：A链为1→2→3→4，B链为6→3→4。值相等的节点有3和4，但这两条链如果是各自独立构造的两条链，虽然有相同值，实际却不是相交的链表。在LeetCode里构造测试时，两个链表末尾的3和4必须是同一个ListNode对象，才能算相交。本地肉眼判断时容易被值骗了，写代码务必坚持比较引用。

4.3 循环会不会死循环

双指针跳转一定会终止吗？假设两条链都不为空也不相交，但长度都是2。P1路径：A1→A2→B1→B2→None；P2路径：B1→B2→A1→A2→None。两者走完所有节点之后同时到达None，循环终止。没有环的情况下不会死循环。

如果有环呢？这题明确说链表无环。如果把双指针套路硬套到带环链表上，就可能出现指针永远不相等且永远不为空的死循环。所以这题的适用前提就是无环链表，别想着拿去解环形链表那题。

4.4 切换指针的时机是“走到空”还是“走完最后一个节点”

前面提过，pA.next is None时切换会在A链长度为1时出现异常。我专门测过这个写法在两条不相交等长链表上的表现：A只有一个节点，B只有一个节点，二者不同。用“走到最后一个节点就切”的写法：pA指向A1，pB指向B1，不相等；下一步pA.next是None所以pA=headB=B1，pB.next是None所以pB=headA=A1，两者还是不相等；再下一步两者next都是None，同时跳到对方的头节点……这会导致两个指针在两个头节点之间反复横跳，永远退出不了循环。

所以pA = pA.next if pA else headB这种“先走到None再切”的写法才能保证总路程恰好等于a+b+c或a+b，不会出现“提前切换导致少了节点”的长度错配。

4.5 测试用例中构造链表的顺序

还有一个很隐蔽的坑。构造相交链表测试数据时，两条链必须先创建公共尾部的节点，再分别接上各自的前段。如果先创建A链的前段和B链的前段，最后再拼接公共部分，代码上没问题，但很多人会在创建时不小心把公共部分复制成两份节点，导致公共节点各不相同，双指针怎么也找不到交点。我习惯封装一个buildIntersectingLists辅助函数，保证公共部分是同一个对象。

5. 测试先行：我如何构造一套可复现的验证用例

刷题不能只在LeetCode上点提交，本地跑测试能让你更快发现边界问题，也能加深对原理的理解。我自己写算法题时习惯构建一套小的测试框架，这道题也不例外。

5.1 本地测试环境的搭建思路

在本地跑这道题不需要引入任何第三方库，Python自带的unittest就够用。先把ListNode类和Solution类放进一个模块文件，然后封装两个辅助函数：一个根据列表值创建链表，一个创建带相交点的两条链。

def build_list(values): dummy = ListNode(-1) cur = dummy for v in values: cur.next = ListNode(v) cur = cur.next return dummy.next def build_intersect(a_values, b_values, common_values): common_head = build_list(common_values) a_head = build_list(a_values) b_head = build_list(b_values) if a_head is None: a_head = common_head else: cur = a_head while cur.next: cur = cur.next cur.next = common_head if b_head is None: b_head = common_head else: cur = b_head while cur.next: cur = cur.next cur.next = common_head return a_head, b_head, common_head

这里的关键是common_head只创建一次，两条链共享同一批节点。a_values和b_values里不包含公共部分的值，分别构建好后，把它们的尾节点接到public_head上，形成Y形结构。

5.2 覆盖核心场景的测试用例表

我准备了几类用例，基本能把这道题的所有分支都照顾到：

T7是专门用来验证“比较引用而非比较值”的用例。两条链的值都是1，但是各自构造的节点，预期结果必须是None。如果你的代码误用==比较节点，这个用例会直接暴露问题。

5.3 用一段代码批量验证

import unittest class TestIntersectionNode(unittest.TestCase): def setUp(self): self.solution = Solution() def test_normal_intersection(self): a_head, b_head, expected = build_intersect([1,2,3], [4,5], [6,7]) self.assertIs(self.solution.getIntersectionNode(a_head, b_head), expected) def test_intersect_at_a_head(self): a_head, b_head, expected = build_intersect([], [1], [8,9]) self.assertIs(self.solution.getIntersectionNode(a_head, b_head), expected) def test_one_contains_other(self): common = build_list([3,4]) a = build_list([1,2]) a.next.next = common b = common result = self.solution.getIntersectionNode(a, b) self.assertIs(result, common) def test_no_intersection(self): a = build_list([1,2]) b = build_list([3,4]) self.assertIsNone(self.solution.getIntersectionNode(a, b)) def test_empty_heads(self): self.assertIsNone(self.solution.getIntersectionNode(None, build_list([1,2]))) def test_single_same_node(self): node = ListNode(1) self.assertIs(self.solution.getIntersectionNode(node, node), node) def test_single_diff_node_same_val(self): self.assertIsNone( self.solution.getIntersectionNode(ListNode(1), ListNode(1)) ) if __name__ == "__main__": unittest.main()

这里所有断言用的都是assertIs和assertIsNone，就是为了坚持“引用比较”这条语义。跑完这一套，你的实现如果全绿，提交LeetCode基本不会翻车。

5.4 测试结果怎么解读

T2这个用例值得单独说一下。A链为空，B链为[1]，公共部分为[8,9]。实际构造结果是A链直接就是公共部分，B链是1→8→9。双指针走法：pA从公共头8出发，pB从1出发。pA先走完公共部分后跳到B链表头1，pB走到公共部分8。两者不相等，继续走。pA在B链上从1走到8，pB从8走到9。继续走，pA从8走到9，pB从9走到None并跳到A链头8。此时pA在9.next也就是None？我用文字推演容易乱，但测试代码跑出来的结果是正确的，且循环会在有限步数内收敛到公共头节点。建议你自己在本地断点跑一遍，跟踪pA和pB的每一步位置，这个动态过程比看任何解释都直观。

6. 从这题延伸出去：双指针思路能解决的一类链表问题

这道题虽然只是easy模式，但它背后的“双指针在不同起点上找交点”思路，可以平移去解决好几道经典链表题。刷完这一题，顺手把相关题型串起来，效率会高很多。

6.1 同款思路能解决哪些题

• 环形链表检测：快慢指针同时从head出发，一个走两步一个走一步，如果相遇说明有环。这和相交链表的双指针本质一样，都是利用“不同速度或不同路程的指针最终能在某个位置相遇”。
• 寻找链表的中点：快指针走两步、慢指针走一步，快指针到达尾部时慢指针正好在中点。这是“路程差”的经典应用。
• 删除链表的倒数第N个节点：先让一个指针走N步，然后两个指针同步前进，先走的指针到了底部，后走的指针正好在待删除位置。这和相交链表里“先让一个指针走完一段，再同步前进”的模式完全一致。

理解相交链表里的“交换路线补足路程”，再去学后面这些题，会有一种“套路都是通的”感觉。

6.2 哈希法什么时候更好

虽然原题要求O(1)空间，但现实中并不是所有场景都要严格遵守这个限制。如果链表非常大，而内存很充足，哈希集合的O(m)空间可以接受，代码更直白，不容易出错。反过来，在嵌入式或者内存受限的系统里，双指针版就是唯一选择。

还有一个视角：面试时先说出哈希集合的直观做法，再优化到双指针，往往比一上来就甩双指针更让面试官舒服。因为前者展示了你“能快速给出可行方案”的能力，后者展示了你“能理解限制条件并优化”的能力。两个都准备比只准备一个稳妥。

6.3 我的练习建议

我自己的刷题习惯是：一道题至少写三遍。第一遍看题解后照着实现，第二遍隔天不看题解独立写，第三遍尝试给其他人讲清楚原理。相交链表这题特别适合第三遍——因为它的代码太短，很容易让人误以为“会写代码=会这题”，能用自己的话把路程补足讲明白，才算真正掌握。

下一步可以做的扩展练习是：把双指针解法改成递归版本，或者增加一个“返回相交节点的索引值”的变体需求。这些花式改法不会改变核心思路，但会迫使你更细致地思考链表结构本身，对后续做更复杂的链表题很有帮助。

最后说一点个人体会。我见过很多人在链表题上卡住，不是因为算法复杂，而是因为对“节点是对象引用”这个概念不够敏感。相交链表这道easy模式题目，恰好是训练这种敏感度的绝佳素材。它不要求你背复杂公式，也不要求高深的数学基础，只要你能把两个指针走的路程画出来，把比较对象和比较值的区别搞清楚，就能稳定通过所有用例。如果你刷题时总觉得自己“看得懂题解但自己做不出来”，我建议就从这道题开始，把链表的基础补扎实，后面再遇到中等难度的链表题就不会发怵了。