相交链表双指针解法：Go语言实现与数学原理详解

做了这么多年算法题，我越来越觉得，Hot 100里真正让人眼前一亮的设计其实不多，多数是靠熟练度和模板硬解。但160这道相交链表不一样，它属于那种"第一次看到解法会愣一下，想通之后再也不会忘"的题目。题目本身一句话就能说清：给你两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点，如果不存在相交节点则返回 null。难点从来不在理解题意，而在如何把空间复杂度压到 O(1)、把代码写到干净利落。

这道题我在面试里问过别人，也在周赛复盘里见过各种绕弯子的写法，说实话，用 Go 写双指针解法的人不少，但能把这个解法背后的原理讲到位的，十个里不超过三个。大部分人只是背下了"两个指针分别走一遍，相遇就是交点"这个结论，一旦面试官追问一句"为什么它们一定会相遇"，就卡住了。

这篇文章我就围绕这个题，把双指针对撞的数学原理、Go 语言实现里的坑、测试用例怎么设计、以及面试时可以主动展示的细节，完整拆开讲一遍。不管你是刚接触链表的初学者，还是准备冲刺大厂算法轮的选手，应该都能从里面拿到点实在的东西。

1. 相交链表到底在考什么：先搞清楚"相等"的含义

很多人第一眼看到这道题，会下意识觉得它简单。两个链表嘛，嵌套循环逐个比较节点值不就行了？如果只是比较值，那确实简单，但题目说的相交，不是值相等，而是指针相等。这一点如果不先想透，后面所有解法都会跑偏。

1.1 指针相等和值相等是两码事

链表里的每个节点在内存里都有独立地址，两个链表相交，意味着从某个节点开始，它们共享同一段内存节点。换句话说，nodeA == nodeB判断的是地址相同，而不是nodeA.Val == nodeB.Val。

我见过不少初学 Go 的同学写这样的代码：

if p.Val == q.Val { return p }

当场就能被反例打脸。比如两个链表里恰好都有值为 3 的节点，但这两个节点是完全独立的内存对象，它们并没有相交。真正的相交必须满足：遍历到某个节点时，指针变量指向的地址完全一致。

1.2 从几何视角理解链表相交

链表相交有一种很直观的几何图像。把两个链表从尾到头拉直看，它们的形状不是两条平行线，而是一个 Y 字形。前半段各自独立，后半段完全重合。

这里有个容易误解的点：相交链表一定会在某个节点汇合，之后一直共享到末尾。不存在"相交一段之后又分开"的情况，因为每个节点只有一个 Next 指针，一旦共享了某个节点，后续路径就唯一确定了。

所以这道题本质上是问：在两条路上走，能不能找到一个共同入口。最笨的办法是拿哈希表记下 headA 走过的所有节点，再遍历 headB 逐个检查。这个思路是对的，但空间复杂度是 O(n)。双指针解法的高明之处在于，它连哈希表都不用，纯粹利用路程关系让两个指针在交点相遇。

提示：做题之前先在心里默念三遍——比地址，不比值；看形状，Y 字形。

2. 双指针相遇的数学原理：为什么它一定能碰上

我第一次看到双指针解法的时候，第一反应是：这玩意儿是不是碰运气？两个指针速度一样，又在不同长度的链表上走，凭什么就一定能在交点碰头？

后来把路程一列出来，才发现这不是巧合，而是一个很漂亮的等价关系。

2.1 核心思路：把两条链表"拼接"起来

假设链表 A 的独有部分长度为 a，链表 B 的独有部分长度为 b，公共部分长度为 c。那么：

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

双指针的做法是：指针 pA 从 headA 出发，走完 A 之后转到 headB 继续走；指针 pB 从 headB 出发，走完 B 之后转到 headA 继续走。

关键在于，当 pA 走到交点时，它走过的总路程是多少？pA 先走完了自己的链表 A（长度 a + c），然后进入链表 B，再走 b 步就到交点。所以：

• pA 到交点的总路程：a + c + b
• pB 到交点的总路程：b + c + a

这两个值完全相等。

换一种更直观的说法：pA 走的路程是"链表A + 链表B的头部到交点"，pB 走的路程是"链表B + 链表A的头部到交点"。大家走的都是 a + b + c 这么长，而这段路程的终点恰好就是交点。

2.2 为什么换个链表走就能"对齐"起点

双指针法的巧妙之处，本质上是通过交换链表来抹平长度差。

假设 A 比 B 长，那么 pA 会先走完 A 进入 B，而 pB 还在 B 上慢慢走。当 pB 终于走完 B 进入 A 时，两个指针所处的位置有什么特点？

• pA 此时在 B 上已经走了 a 步（因为 A 比 B 长的部分就是 a - b，pA 走完 A 后，比 pB 早出发了 a - b 步；当 pB 走完 B 时，pA 在 B 上已经走了 a 步中的一段，再仔细算一下会发现两者离交点的剩余距离相等）。

这个推导有点绕，我更习惯用"总路程相等"来理解：两个指针最终都会走 a + b + c 步，走完这多长路程时，它们位于同一个节点——交点。因为从各自的起点出发，沿着各自路线走同样长的路程，而这段路程的终点被设计成同一点。

2.3 无交点的情况：它们会在 null 相遇

如果两个链表根本不相交，也就是 c = 0，情况会怎样？

pA 走完 a + b，恰好走到 null；pB 走完 b + a，也恰好走到 null。两个指针在 null 处相遇，此时返回 null 即可。这个结论非常干净，不需要额外标记，不需要计数器。

我当年第一次推到这里时，有种"原来如此"的感觉。后面的 Go 实现只有三行核心代码，但每一行都建立在这套路程等式之上。

提示：双指针法的命名很容易和"快慢指针"混淆，但这里两个指针速度相同，靠的是路程相等而非速度差，这是两种完全不同的思路。

3. 从暴力解法到双指针：为什么最终选择这条路

在给出最终代码之前，我想先聊聊其他解法，因为只有对比过，才知道双指针的价值在哪里。刷题不是背答案，而是知道每一条路为什么好、为什么差。

3.1 哈希表解法：简单但空间不达标

用哈希表做这道题，思路非常直白：

1. 遍历 headA 的所有节点，把每个指针存入 map
2. 遍历 headB，逐个检查当前节点是否在 map 中
3. 第一个命中的节点就是交点；如果走到头都没有，返回 null

Go 代码写出来大概是这样：

func getIntersectionNode(headA, headB *ListNode) *ListNode { seen := map[*ListNode]bool{} for p := headA; p != nil; p = p.Next { seen[p] = true } for p := headB; p != nil; p = p.Next { if seen[p] { return p } } return nil }

这段代码没毛病，时间复杂度 O(m + n)，但空间复杂度是 O(m)。在 LeetCode 上能过，在面试里也能拿一个"可以，但能不能优化空间"的评价。如果你想展示更强的代码能力，就得往 O(1) 空间的方向走。

3.2 先算长度差的解法：正确但不够优雅

还有一部分人会选择先求两个链表的长度，然后让长链表的指针先走长度差，再两个指针同步前进。思路也不复杂：

• 遍历两个链表，得到长度 lenA 和 lenB
• 较长的链表指针先走 |lenA - lenB| 步
• 然后两个指针同步前进，第一个相等的节点就是交点

这种解法的时间复杂度同样是 O(m + n)，空间 O(1)。但它需要先完整遍历一遍两个链表求长度，整体代码量会比双指针法多不少，而且逻辑分了好几段，面试时写起来容易漏掉一些边界判断。

双指针法的高明之处在于，它把"对齐起点"这件事隐含在路程交换里，连长度都不用数。

3.3 双指针的实际价值不止于空间

如果从纯工程角度看，多遍历一次链表其实无所谓，链表本来就不长，空间 O(n) 也就多存 n 个指针。那为什么面试官偏爱双指针解法？

我认为有两个原因。

第一，它体现的是对问题结构的理解。你能从"路程等式"这个层面去思考问题，而不是停留在"哈希表查重"这个套路化的方案上。面试官想看到的就是这种思维深度。

第二，它的代码极其精简，几乎不可能写错。你告诉面试官"两个指针各走一遍，相遇就是答案"，然后用三行代码证明这一点，这种干净利落的表达本身就很有说服力。

从工程角度说，在嵌入式系统或内存受限的环境里，O(1) 和 O(n) 的差别是实质性的；从面试角度说，双指针解法传递的信息量也完全不一样。

4. Go 语言实现：三行核心代码与真实测试

说了一大堆原理，现在上代码。我用 Go 实现的双指针解法，核心逻辑非常短，但我还是会把完整的函数体和测试都贴出来，因为光是核心三行，初学者往往不知道循环条件为什么那样写。

4.1 双指针的核心代码

func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } pA, pB := headA, headB for pA != pB { if pA == nil { pA = headB } else { pA = pA.Next } if pB == nil { pB = headA } else { pB = pB.Next } } return pA }

有没有注意到第一行就做了空指针判断？这是 Go 里必须养成的好习惯，后面我会专门讲。先把核心逻辑拆一下：

• pA和pB各自从链表头出发
• 每轮循环，两个指针各走一步
• 走到末尾就跳到对方的链表头继续走
• 当pA == pB时，要么是交点，要么是 null，直接返回

这个写法最直观，也最好讲清楚。不过如果你追求极致的简洁，可以把指针切换那一段压缩一下，写成下面这样，面试时手写会更省时间：

func getIntersectionNode(headA, headB *ListNode) *ListNode { pA, pB := headA, headB for pA != pB { if pA == nil { pA = headB } else { pA = pA.Next } if pB == nil { pB = headA } else { pB = pB.Next } } return pA }

把 nil 判断去掉之后，代码确实短了，但可读性下降了。我在 LeetCode 上提交时两种写法都能过，不过如果是面试现场，我更推荐保留 nil 判断的版本，因为你可以顺势向面试官解释"这是对链表题的基本敬畏"。

4.2 为什么循环条件必须是 pA != pB

这是我被问过的一个高频问题：for pA != pB这个条件，如果两个链表根本不相交，会不会死循环？

不会。回到第 2 节的数学推导，当两个链表不相交时，pA 在走完 a + b 步后等于 nil，pB 在走完 b + a 步后也等于 nil，两个 nil 的地址是一样的，循环自然退出。

这个点一定要能在面试时讲清楚。因为很多人代码背下来了，但问他"如果没交点会怎样"，他会愣住。你要能立刻回答：无交点时 c=0，路程等式仍然成立，只不过终点是 nil，循环照样能退出。

4.3 性能实测和提交记录

我实际在 LeetCode 上提交过这个解法，数据是：

• 时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度。每个指针最多遍历两个链表各一次
• 空间复杂度：O(1)，只用了两个指针变量，没有额外容器

这个表现已经是最优的了。哈希表版本虽然也是 O(m + n)，但空间多了一倍，实际运行耗时也会因为 map 的哈希计算而略高。另外，Go 的 GC 压力也更小，因为不需要维护一个临时 map。

提示：提交时注意题目给的函数签名，Go 版本的 ListNode 结构体通常是这样的：

type ListNode struct { Val int Next *ListNode }

5. 这些边界条件，我在笔试和面试里都踩过

链表的边界条件永远是重灾区。相交链表这道题表面上友好，但真要你在白板上从头撸一遍，有四个位置特别容易翻车。我把自己踩过的和看别人踩过的坑整理出来，你可以直接拿来当 checklist。

5.1 一个链表为空：直接返回 null

这是最容易被忽略的 corner case。两个链表中只要有一个是空的，就不可能有交点，直接返回 nil。

我在早期刷题的时候经常不写这个判断，结果就是pA.Next在 nil 上调用，直接 panic。Go 里对 nil 指针的Next操作是运行时报错，不像有的语言会给你一个 undefined 或者 null，所以这种错误在本地一跑就崩，非常尴尬。

if headA == nil || headB == nil { return nil }

这行代码不是可有可无的防御，而是逻辑上的必要前置条件。

5.2 链表的头节点就是交点：双指针能直接抓到吗

能。如果 headA 和 headB 指向同一个节点，那么在循环的第一次判断时，pA == pB就成立了，直接返回该节点。

这个 case 你可能觉得理所当然，但注意：这恰好验证了双指针法不需要任何额外操作。有些解法如果先"交换链表"再做比较，反而会在这种场景下出 bug——比如先让某个指针走完整个链表再进入另一条链，那第一次相遇就可能不是头节点了。

双指针法天然适合这个 case，因为比较发生在每次移动之前，包括初始状态。

5.3 一个链表完全包含另一个：不要用长度差误判

想象链表 A 长 5，链表 B 是 A 的后半段，也就是它们从头就共享了一段。这个 case 下，双指针法依然能正确返回交点，因为 pA 和 pB 在某个位置开始同步，不断逼近，最终相遇。

但是如果你使用"先求长度差"的解法，就要小心：长度差算出来之后，你让长链表的指针先走，此时短链表的头节点可能已经就是交点了。如果你写成"等长之后才开始比较"，那就会漏掉这个 case。正确做法是每走一步就判断一次相等性。

这点我特别想强调，因为网上很多题解在讲长度差法时，代码里是用for pA != pB { pA = pA.Next; pB = pB.Next }这种结构，但漏了先判断初始状态。

5.4 无交点且长度相同、长度不同：都要走到 nil 收尾

我把这两个 case 合并是因为它们走向的结论是一样的：循环最终退出时 pA 和 pB 都为 nil，返回 nil。

我自己写测试用例时，通常会同时覆盖这两类场景，确保没有死循环，也确保返回值是 nil 而不是某一个链表的尾节点。

// 无交点，长度相同 a1 := &ListNode{Val: 1} a2 := &ListNode{Val: 2} b1 := &ListNode{Val: 3} b2 := &ListNode{Val: 4} a1.Next = a2 b1.Next = b2 // getIntersectionNode(a1, b1) 应该返回 nil

// 无交点，长度不同 a1 := &ListNode{Val: 1} a2 := &ListNode{Val: 2} a1.Next = a2 b1 := &ListNode{Val: 3} // getIntersectionNode(a1, b1) 应该返回 nil

如果这两组测试都过了，基本可以放心提交。

6. 进阶思考：如果面试官继续追问，你还能说什么

一道简单题，如果只是说出答案，面试官很难判断你的真实水平。但如果他能顺着你的解法往下问，而你能接住，那这道题的价值就被放大了。我梳理了几个常见的追问方向，每个方向都有对应的回答思路。

6.1 能不能用 Go 的==直接比较两个结构体指针

能，而且这在 Go 里是合法的。Go 允许对指针变量做==比较，判断的是两个指针是否指向同一块内存地址。这正是我们需要的语义。

不过要注意，Go 的map[*ListNode]bool中，指针作为 key 也是按地址比较的，所以哈希表解法天然可用。这一点比某些语言方便，比如在 Java 里你还需要注意 hashCode 和 equals 的实现，在 Go 里完全不操心。

6.2 如果题目改成"两个链表是否有环"，双指针还能用吗

能，但要换成快慢指针。判断链表是否有环的经典做法是：快指针每次走两步，慢指针每次走一步，如果相遇说明有环。这和本题的"同速双指针交换链表"是完全不同的策略。

面试官这么问通常是想试探你是否理解不同场景下不同指针策略的差异。我的回答模板是：相交链表靠的是路程等式，环检测靠的是速度差，两者都是双指针，但底层数学逻辑不一样，不能混用。

6.3 如果两个链表都可能有环，这题应该怎么解

这是一个进阶变体，LeetCode 上有一道题叫"两个链表相交 II"的加强版就是这个场景。思路是先分别检测两个链表是否有环，找到入环点，然后分情况讨论：无环走常规双指针；有环则判断是否共享环，如果共享，交点在环之前或环上。

这个题我建议感兴趣的读者自己推一遍，因为它能帮你把相交链表、环检测、双指针三个知识点串起来。我当时推完这个变体之后，再回头看 160 这道题，感觉整个链表题的思路完全通了。

6.4 从这道题延伸出去的同类题目

• 141. 环形链表（检测链表是否有环）
• 142. 环形链表 II（找到入环点）
• 面试题 02.07. 链表相交（基本和 160 一样）
• 剑指 Offer 52. 两个链表的第一个公共节点（同样思路，只是语言描述不同）

这几道题如果能一口气全部用 O(1) 空间做出来，链表题入门阶段就算过关了。

7. 我总结的一些经验之谈

最后聊一些不一定能写在题解里、但对实际刷题和面试很有帮助的东西。

7.1 画图永远比背代码有效

相交链表的所有解法，核心都在那张 Y 字形图上。我刷题的时候会把链表画成一条条线段，用不同颜色标出 a、b、c 三段，然后拿笔模拟指针移动。多推几遍之后，你会发现代码变成了一种自然表达，而不是需要记忆的符号串。

现在很多刷题网站支持可视化调试，我强烈建议初学者别急着看题解，先自己画图推演。这道题画图推演十分钟，胜过背代码十遍。

7.2 Go 刷题时的几个好习惯

• 拿到链表题，第一件事检查是否为空，这是保命代码
• 修改指针之前想清楚，当前节点是否可能为 nil
• 控制台打印节点地址时用%p，看地址比看值更直观
• 写完代码之后，先跑两个 case：空链表和单节点链表，再提交

这些习惯看着琐碎，但在面试白板编程时，它们就是你和"背题党"的分水岭。

7.3 关于 Hot 100 的刷题策略

Hot 100 我完整刷过一遍，感受是：真正值得反复研究的题其实不超过三成，相交链表算一道。因为它涉及的思路可以迁移到很多场景，比如判断两个字符串是否由相同字符集构成、合并有序链表的变体、甚至一些滑动窗口问题里"对齐位置"的思想。

我的建议是，一道题不要做完就翻篇，花十分钟想清楚三个问题：

1. 暴力解为什么不够好
2. 最优解好在哪
3. 如果把条件改一下，解法还能不能work

这三个问题想透了，一道题顶五道。相交链表这道题，这三个问题恰好都有清晰答案，这也是我把它作为"值得精做"题目的原因。