做了这么多年算法题我越来越觉得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 bpB 到交点的总路程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 - bpA 走完 A 后比 pB 早出发了 a - b 步当 pB 走完 B 时pA 在 B 上已经走了 a 步中的一段再仔细算一下会发现两者离交点的剩余距离相等。这个推导有点绕我更习惯用总路程相等来理解两个指针最终都会走 a b c 步走完这多长路程时它们位于同一个节点——交点。因为从各自的起点出发沿着各自路线走同样长的路程而这段路程的终点被设计成同一点。2.3 无交点的情况它们会在 null 相遇如果两个链表根本不相交也就是 c 0情况会怎样pA 走完 a b恰好走到 nullpB 走完 b a也恰好走到 null。两个指针在 null 处相遇此时返回 null 即可。这个结论非常干净不需要额外标记不需要计数器。我当年第一次推到这里时有种原来如此的感觉。后面的 Go 实现只有三行核心代码但每一行都建立在这套路程等式之上。提示双指针法的命名很容易和快慢指针混淆但这里两个指针速度相同靠的是路程相等而非速度差这是两种完全不同的思路。3. 从暴力解法到双指针为什么最终选择这条路在给出最终代码之前我想先聊聊其他解法因为只有对比过才知道双指针的价值在哪里。刷题不是背答案而是知道每一条路为什么好、为什么差。3.1 哈希表解法简单但空间不达标用哈希表做这道题思路非常直白遍历 headA 的所有节点把每个指针存入 map遍历 headB逐个检查当前节点是否在 map 中第一个命中的节点就是交点如果走到头都没有返回 nullGo 代码写出来大概是这样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 步后等于 nilpB 在走完 b a 步后也等于 nil两个 nil 的地址是一样的循环自然退出。这个点一定要能在面试时讲清楚。因为很多人代码背下来了但问他如果没交点会怎样他会愣住。你要能立刻回答无交点时 c0路程等式仍然成立只不过终点是 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 从这道题延伸出去的同类题目环形链表检测链表是否有环环形链表 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 我完整刷过一遍感受是真正值得反复研究的题其实不超过三成相交链表算一道。因为它涉及的思路可以迁移到很多场景比如判断两个字符串是否由相同字符集构成、合并有序链表的变体、甚至一些滑动窗口问题里对齐位置的思想。我的建议是一道题不要做完就翻篇花十分钟想清楚三个问题暴力解为什么不够好最优解好在哪如果把条件改一下解法还能不能work这三个问题想透了一道题顶五道。相交链表这道题这三个问题恰好都有清晰答案这也是我把它作为值得精做题目的原因。