这题是我在刷LeetCode Hot100时遇到的第18道题说实话题目本身不算难但一个“相交”的定义容易让人绕进去——很多人一开始会误以为比较链表节点的值就行结果一跑用例就傻眼。等我把双指针解法真正弄明白之后才发现这道题其实是在考察一个非常巧妙的逻辑如何让两条长度不同的链表在走到相同位置时能够“对齐”。这篇文章就把我从读题到写出最优解的全过程、踩过的坑、以及测试用例的构造方法都梳理一遍给正在为Hot100冲刺的人一个可直接参考的完整记录。1. 先搞清楚题目在问什么相交不是“值相等”是“地址重合”1.1 相交链表的图形结构LeetCode 160题名“Intersection of Two Linked Lists”也被人译作相交链表。题目给出的不是两条完全独立的链表而是形如下面这种结构两条链表从某个节点开始合流之后共享一组相同的节点。画出来就是这样的关系链表Aa1 - a2 - c1 - c2 - c3链表Bb1 - b2 - b3 - c1 - c2 - c3这里的c1是两条链表的交点从c1开始一直到c3这些节点在内存中是同一组节点并不是复制出来的两套。题目要求返回一个ListNode指针指向c1如果两条链表没有交点返回null。1.2 为什么不看值的比较这条题最大的迷惑性也在这里有些人一看c1、c2、c3的值都一样就想着直接比较节点的val。但LeetCode官方用例中并没有保证链表节点的值唯一两个不同节点完全可能存放相同的值。就算两个节点的值相同它们也只是长得像地址不同不算“相交”。真正的判定方式是看引用相等也就是指针地址相等。你拿到的链表A中的某个节点cur如果它和链表B中的某个节点是同一个指针那才说明这两条链表在物理上发生了交会。1.3 题目的三个隐藏约束根据题目的进阶要求读题时还要注意几个关键点链表结构不能改动也就是不能在解题过程中把A的尾节点强行连到B的头上题目允许使用额外的空间来解题但要求你能给出时间复杂度O(nm)、空间复杂度O(1)的解法如果两条链表不相交要能正确返回null不能陷入死循环。前两条直接决定了解法的大方向你要不就用哈希表换时间要不就得在不占用额外空间的前提下设计一种“双子指针”的同步策略。我当时刷到这道题时第一反应是“这题是不是有病明明用Set就能做还要什么O(1)空间”后来理解了双指针的核心逻辑才明白出题人到底在考察什么。2. 哈希表解法五分钟能写出来的保底方案2.1 用Set记录地址的核心逻辑哈希表解法的思路非常直接先把链表A的所有节点都放进一个HashSet里然后遍历链表B的每一个节点检查这个节点是否已经存在Set里。一旦发现存在说明这个节点就是两条链表共享的起点如果遍历完整个B链表都没找到说明两条链表没有交集。这个做法最核心的假设是在Python、Java这类语言中Set存放的是节点的引用信息不是节点值。所以在存入时是以当前节点的整体身份存入而不是当前节点的val。2.2 代码实现class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: visited set() cur headA while cur: visited.add(cur) cur cur.next cur headB while cur: if cur in visited: return cur cur cur.next return None这段代码在逻辑上没有任何问题我最初提交时就是这么写的也是一次通过。时间复杂度O(mn)空间复杂度O(m)其中m是链表A的长度。2.3 复杂度与不优雅之处哈希表解法最大的问题在于额外空间。虽然题目的基本要求允许O(m)空间但Hot100里很多题都有“能不能优化到O(1)空间”的引申问题面试官在讲这道题时通常会紧接着问你还能不能再省点空间。省空间意味着不能用Set不能用栈也不能用数组记录访问过的节点。那能怎么做呢只能靠指针自身的挪动来模拟一种“对齐”效果。这就自然引出了双指针解法。我在实际整理题目清单时发现哈希表解法适合作为“保底方案”记录在题解中因为它思路简单、不容易出错、好调试。但你如果只写出这个版本面试时大概率会被追问追问的过程其实就是考察对双指针思想的理解深度。3. 双指针解法两条链各自走一遍走过的路就能抵消长度差3.1 核心观察路径互补双指针解法是所有解法里最漂亮的一个也是我最终记笔记时采用的版本。它的思路可以这样描述让pA指针从headA出发pB指针从headB出发。各自沿着自己的链表一个节点一个节点向后移动。当pA走到自己链表的尾部时让它跳转到headB继续走当pB走到自己链表的尾部时让它跳转到headA继续走。这里的关键在于“跳转”。做了两个指针的跳转后pA和pB各自走过的路径总长度就会变成pA走过的路径链表A全部节点 链表B的非公共部分pB走过的路径链表B全部节点 链表A的非公共部分如果两条链表有交点假设公共部分的长度为c链表A的非公共部分长度为a链表B的非公共部分长度为b那么两条链表的长度分别是ac和bc。pA走到交点时实际走过的节点数为a c b pB走到交点时实际走过的节点数为b c a仔细一看这两个值是相等的都是abc。也就是说当pA和pB同时走完这段路程时它们会同时到达交点。这个结论本身非常朴素但它的好处让人惊喜我们不需要知道两条链表长度差的具体数值也不需要事先计算长度只需要让两个指针各自走一遍对方的链表长度差就在路径中自动抵消了。3.2 证明为什么必定同时到达交点假设两条链表在c1节点相交链条如下A路径a1 - a2 - ... - a_a - c1 - c2 - ... - c_c B路径b1 - b2 - ... - b_b - c1 - c2 - ... - c_cpA从a1出发走完A的非公共部分a个节点后到达c1接着走公共部分c个节点到尾部然后跳转到B的头节点再走B的非公共部分b个节点最后又到达c1。整个过程走的路程是 a c b。pB从b1出发同理走完B的非公共部分b个节点后到达c1接着走公共部分c个节点到尾部然后跳转到A的头节点再走A的非公共部分a个节点最后同样到达c1。整个过程走的路程是 b c a。由于加法交换律acb和bca完全相同所以两个指针在走完这段路程的瞬间必然同时抵达交点c1。这里要特别注意两个指针并不是“谁先到交点等谁”而是“在同一时刻同时到达”。因为每一轮循环中pA和pB都只向前走一步它们不会被跳过也不会停留所经历的时间步数完全一致所以当走过的总步数相同时自然就相遇了。3.3 无交点时的行为如果两条链表不相交呢这是另一个容易卡住的点。假设链表A长度为m链表B长度为n。pA走完A的m个节点后跳转到B接着再走完B的n个节点pB走完B的n个节点后跳转到A接着再走完A的m个节点。最终pA走过了mn个节点pB也走过了nm个节点它们在同一个时间点各自到达自己路径的末尾也就是null。此时pA和pB都是null两者相等循环退出返回null即可。代码中的循环条件就是while pA ! pB。当pA和pB都指向null时条件不成立循环结束返回pA的值null。3.4 完整代码class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - 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都只移动一步没有额外的长度计算没有额外的数组或集合空间复杂度严格O(1)。我第一次看到这个版本的代码时有个地方困惑了很久万一两条链表有一方是空链表会不会死循环答案是不会。我们来推演一下headA为nullheadB不为nullpA初始为nullpB初始为headB进入循环后pA被赋值为headBpB前进一位继续循环。最终pB到达nullpA也在走完B的所有节点后到达null两者同时为null循环退出返回null。如果headA和headB都为null循环条件一开始就不满足直接返回null。所以这段代码在任何边界输入下都不会死循环这也是它能被广泛接受的原因之一。4. 刷题时最容易翻车的细节边界情况与测试用例构造4.1 空链表与单节点链表我在本地调试时最常犯的错误是没有考虑空链表。如果headA为null那无论headB是什么两链表都不可能相交。代码当然能正确处理这种情况但你要在本地额外验证一遍才不会怀疑自己。单节点链表也是容易被忽视的边界如果两条链表都只有一个节点且这个节点是同一个节点那么pA初始就是交点pB也是交点循环条件pA ! pB不成立直接返回该节点逻辑没问题如果两个节点地址不同即使值相同pA和pB也要走几轮后同时变成null返回null。4.2 两链表完全没有交集没有交集时双指针会各自走完mn个节点然后相遇在null处。这一点我在第一次推导时总是想错因为总有一个念头跑出来pA先走完A跳转到B走完B之后会不会因为走到B的开头而发现自己在B里遇见了原本属于A的节点这种担心是多余的。因为“没有交集”意味着A和B的节点在内存地址上完全不重合不管pA怎么跳转它看到的节点要么属于A要么属于B永远不能通过比较自身先后遇到的节点来产生交集。最终两者都到null就返回null。4.3 值相同但地址不同的迷惑场景这是最有迷惑性的测试用例。两条链表每个节点的值都一样例如A是1-2-3B是1-2-3两条链表结构完全一样但节点在内存中是两份独立的。许多初学者用值比较会误判为相交而用哈希表也会出现一个问题如果把节点的val放进Set而不是节点本身那也会误判。正确做法是把节点本身放进Set哈希表解法中我写的是visited.add(cur)而不是visited.add(cur.val)这就是区分两种不同“相等”概念的地方。双指针解法天然避免了这个坑因为它只比较指针的地址不比较值。4.4 手动构造相交链表的测试用例在本地刷题时我经常需要自己构造相交链表来验证。这里分享一个我常用的构造方式# 构造公共尾部 common ListNode(8) common.next ListNode(10) # 构造链表Aa - common headA ListNode(4) headA.next ListNode(1) headA.next.next common # 构造链表Bb - common headB ListNode(5) headB.next ListNode(6) headB.next.next ListNode(7) headB.next.next.next common这样headA和headB就共享了common及以上节点交点就是common。你可以把这个构造过程写成一个辅助函数用于本地调试。验证时除了打印返回值我还会打印返回节点的值防止因为地址比较错误导致返回的是其他节点。5. 把这道题的经验带走双指针技巧的通用性5.1 环形链表检测与相遇思想刷到这道题时你大概率已经或即将遇到另一道经典题141环形链表。环形链表的快慢指针解法和相交链表的双指针解法本质上都用了同一种思想——通过指针在道路上行走的路径设计让某种条件自动达成。环形链表靠快指针每次走两步、慢指针每次走一步来制造“速度差”让两者在环内必然相遇相交链表靠两个指针分别走完两条链表再互换路径来制造“路径长度一致”让两者在交点必然相遇。两者的代码都很短但背后的推导逻辑都要写清楚才能在面试时讲明白。5.2 快慢指针的其他经典应用双指针思想在链表题里的应用远不止这两道删除链表的倒数第N个节点可以先用快指针走N步再让快慢指针同步走快指针到底时慢指针正好在倒数第N个节点前找链表的中点可以让快指针每次走两步慢指针每次走一步快指针到底时慢指针在中点判断回文链表可以结合快慢指针找中点再反转后半段。如果你把160题作为Hot100的第18题来刷那接下来的链表题大概率会用到这些变形。我在刷完这道题之后又把141环形链表重新整理了一遍发现两者放在一起理解比单独刷效果好得多。5.3 我个人的练题心得我在整理题解笔记时会把每道题分成几个部分题意重述、最直观解、最优解、为什么最优解是对的、边界情况、类似题目。相交链表这道题的“为什么最优解是对的”部分我写的是上面那段路程长度的推导不是简单抄一遍代码就完事。回顾这道题本身我最想分享的心得是**双指针解法虽然代码只有四行但它的正确性是靠“路径总长度相等”来保证的不是靠运气。**很多人面试时紧张就背代码结果面试官随便改个条件问“如果两个链表不相交呢”就答不上来。你只要把a、b、c三段路程画出来现场推一遍面试官就会很满意。如果你现在正在刷Hot100建议你不要跳过这道题也不要只写哈希表解法。花一晚上把双指针的推导过程吃透再把代码默写一遍训练出来的不是这道题的答案而是一种处理链表问题时的“路径设计”思维。这种思维会在后续很多链表题里反复用到。就我个人的刷题节奏而言160题属于“看起来简单但值得细品”的题目按Hot100顺序刷到第18题时你的链表基础已经积累得差不多正好借这道题顺手打通双指针这一类问题的底层逻辑。