1. 从一道题看链表相交的本质链表相交这个问题在算法题里算是那种看起来简单、写起来容易翻车的典型。我刷 LeetCode 那会儿第一次看到相交链表这个标题脑子里第一反应是两个链表相交不就是找第一个公共节点吗结果真动手写的时候边界情况一个接一个地冒出来指针走着走着就不知道跑哪去了。这道题的核心场景很明确给你两个单链表的头节点headA和headB判断它们是否相交如果相交就返回相交的起始节点不相交就返回null。听起来像是一道纯粹的指针操作题但它背后考察的东西其实挺多——空间复杂度的取舍、双指针的数学直觉、以及边界条件的处理能力。为什么这道题值得单独拿出来讲因为它是链表类题目里少有的可以用多种思路解、但最优解非常优雅的代表。暴力哈希表能做但空间复杂度 O(n)双指针法能做到 O(1) 空间而且代码短到只有几行。这种用数学思维把空间省下来的解法在实际工程里处理内存敏感的场景时思路是可以直接迁移的。适合谁来参考这篇内容如果你刚开始刷链表题对指针操作还不够熟练这篇会帮你把每一步走位讲清楚如果你已经刷过一遍但总是记不住双指针的推导逻辑这篇会从数学角度把为什么两个指针走的总路程相等这件事讲透。Java 和 Python 两个版本的代码我都会给出来并且逐行注释关键点。2. 相交链表的判定逻辑与方案选型2.1 相交的本质Y 字形而非 X 字形很多人第一次理解链表相交时会有一个误区以为两个链表可以像两条直线一样交叉成 X 形中间交叉一下然后各自继续延伸。但在单链表的结构下这是不可能的。原因在于单链表的每个节点只有一个next指针。一旦两个链表在某个节点处相交那个节点之后的所有节点都是共享的因为从相交节点开始next的指向是唯一的。所以两个相交链表的结构一定是 Y 字形——上面两个分叉下面合并成一条。这个认知非常关键它直接决定了后面所有解法的正确性。如果你脑子里想的是 X 形那你会觉得相交节点之后可能又分开从而写出错误的判断逻辑。提示判断链表相交只需要看两个链表的尾节点是否相同。如果尾节点相同一定相交如果尾节点不同一定不相交。这是所有解法的基础前提。2.2 三种解法的取舍分析面对这道题通常有三条路可以走我分别说一下它们的适用场景和取舍逻辑。第一种暴力双重循环。固定链表 A 的一个节点遍历链表 B 看是否有相同节点然后移动 A 到下一个重复。时间复杂度 O(m*n)空间 O(1)。这个解法在面试里基本不会加分但作为保底思路可以先说出来展示你有解题方向。第二种哈希表记录法。先遍历链表 A把所有节点存入一个哈希集合注意存的是节点对象本身不是节点的值。然后遍历链表 B第一个在集合中出现的节点就是相交起始节点。时间复杂度 O(mn)空间复杂度 O(m)。这个解法思路直观代码好写面试里可以作为第一版答案。第三种双指针法。这是最优解时间 O(mn)空间 O(1)。核心思路是让两个指针分别从两个头节点出发走到末尾就切换到另一个链表的头部继续走。当两个指针相遇时就是相交节点。为什么双指针法能成立这里有一个很漂亮的数学推导我在下一节详细展开。2.3 为什么优先选双指针法从工程角度看哈希表法在大多数场景下已经够用了毕竟现在的机器内存都不小。但双指针法的价值在于两点一是它展示了你对链表结构的深刻理解二是它把空间压到了常数级在处理超长链表或者内存受限的嵌入式场景时这个优势是实打实的。我个人的习惯是面试时先说哈希表法快速给出可行解然后主动提出我可以优化空间复杂度到 O(1)再写双指针法。这样既展示了思路的完整性又展示了优化能力。3. 双指针法的数学推导与核心细节3.1 走位逻辑的数学证明假设链表 A 的独立部分长度为 a从 headA 到相交节点的距离链表 B 的独立部分长度为 b两个链表的公共部分长度为 c。那么链表 A 的总长度是 a c链表 B 的总长度是 b c。现在让指针 pA 从 headA 出发指针 pB 从 headB 出发速度相同每次各走一步。当 pA 走到链表 A 末尾时它走了 a c 步然后切换到 headB 继续走。当 pB 走到链表 B 末尾时它走了 b c 步然后切换到 headA 继续走。关键来了pA 走的总路程是 (a c) bpB 走的总路程是 (b c) a。这两个值都等于 a b c。也就是说当两个指针都走完 a b c 步时它们必然同时到达相交节点。如果两个链表不相交c 0那么它们会同时到达 null此时返回 null 即可。这个推导的美妙之处在于它不需要你知道 a、b、c 的具体值只需要让两个指针走对方走过的路就能自然对齐。3.2 边界条件处理清单双指针法代码很短但边界条件如果不注意很容易出问题。我整理了一份检查清单两个链表都为空直接返回 null代码里循环条件会自然处理。其中一个为空同上指针切换后会在 null 处相遇。两个链表不相交两个指针最终会同时变成 null循环结束返回 null。相交节点就是头节点比如两个链表从第一个节点就共享此时 a 0 或 b 0双指针第一轮就能相遇。链表只有一个节点需要确保指针切换逻辑不会导致死循环。注意循环的终止条件是pA ! pB而不是pA ! null pB ! null。这一点非常关键因为如果写成后者当两个链表不相交时指针会在 null 处无法正确相遇。3.3 指针切换的写法细节指针切换那一步很多人会写成这样if (pA null) { pA headB; } else { pA pA.next; }这种写法是对的但更简洁的写法是利用三元表达式pA (pA null) ? headB : pA.next;两种写法逻辑完全一样但后者更紧凑。不过我要提醒一点在面试手写代码时建议用第一种展开的写法因为面试官更容易看清你的逻辑不容易因为一行太长而看漏细节。Python 版本因为语法特性可以写得更简洁pA headB if not pA else pA.next但同样建议在面试时展开写清晰优先。4. Java 与 Python 完整实现及逐行解析4.1 Java 版本实现先看 Java 的完整代码我加了详细注释public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 如果任一链表为空直接返回 null if (headA null || headB null) { return null; } // 定义两个指针分别指向两个链表头部 ListNode pA headA; ListNode pB headB; // 当两个指针不相等时继续循环 while (pA ! pB) { // pA 走到末尾就切换到 headB否则继续前进 pA (pA null) ? headB : pA.next; // pB 走到末尾就切换到 headA否则继续前进 pB (pB null) ? headA : pB.next; } // 循环结束时pA 和 pB 要么都指向相交节点要么都为 null return pA; } }这段代码有几个点值得展开说。第一开头的空判断其实可以省略因为如果 headA 为 nullpA 初始就是 null循环条件pA ! pB在 pB 也为 null 时不成立直接返回 null。但如果只有一个为 null另一个不为 null循环会进入然后 pA 切换到 headBpB 继续走最终两个都会变成 null。所以空判断是防御性编程不是必须的但写上更稳妥。第二pA (pA null) ? headB : pA.next;这一行的执行顺序很重要。先判断 pA 是否为 null如果是就切换到 headB否则前进到下一个节点。注意这里切换后不会立即再判断而是等下一轮循环。第三循环结束后的返回值。如果两个链表相交pA 和 pB 会指向同一个相交节点如果不相交两个都会是 null。所以直接返回 pA 即可不需要额外判断。4.2 Python 版本实现Python 版本的逻辑完全一样但语法更简洁class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: # 任一链表为空则直接返回 None if not headA or not headB: return None # 初始化两个指针 pA, pB headA, headB # 当两个指针不相等时循环 while pA ! pB: # pA 走到末尾切换到 headB否则前进 pA headB if not pA else pA.next # pB 走到末尾切换到 headA否则前进 pB headA if not pB else pB.next # 返回相遇节点可能为 None return pAPython 里not pA等价于pA is None因为链表节点对象在布尔上下文中默认为 True只有 None 才是 False。这个写法比pA is None更 Pythonic但在团队协作中如果队友对 Python 特性不熟建议还是写pA is None更明确。4.3 哈希表法作为对照实现为了完整性我把哈希表法的 Java 实现也放出来方便你对比两种解法的差异public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { SetListNode visited new HashSet(); // 先把链表 A 的所有节点存入集合 ListNode cur headA; while (cur ! null) { visited.add(cur); cur cur.next; } // 遍历链表 B找到第一个在集合中的节点 cur headB; while (cur ! null) { if (visited.contains(cur)) { return cur; } cur cur.next; } return null; } }哈希表法的优势是逻辑直观不需要数学推导适合在面试紧张时快速写出可行解。劣势是空间复杂度 O(m)如果链表 A 特别长内存占用会比较明显。4.4 两种解法的性能对比对比维度双指针法哈希表法时间复杂度O(mn)O(mn)空间复杂度O(1)O(m)代码行数约 10 行约 15 行理解难度需要数学推导直观易懂面试加分高中适用场景内存敏感、超长链表快速实现、逻辑清晰优先从表里可以看出来双指针法在空间上有明显优势但理解成本略高。我的建议是两种都要会面试时根据情况选择。5. 实操踩坑记录与常见问题排查5.1 我踩过的三个典型坑第一个坑把节点值相等当成节点相等。刚开始刷题时我写过if (pA.val pB.val)这样的判断结果在链表有重复值的时候直接翻车。相交链表判断的是节点对象是否相同内存地址相同不是节点的值相同。这个错误在 Java 里表现为和equals的混淆在 Python 里表现为和is的混淆。注意Java 里判断节点相同用pA pB引用比较Python 里用pA is pB。不要用值比较。第二个坑循环条件写错导致死循环。我见过有人把循环条件写成while (pA ! null pB ! null)这样当两个链表不相交时指针走到 null 就退出循环了但此时无法区分不相交和还没走完。正确的写法是while (pA ! pB)让指针在 null 处也能相遇。第三个坑指针切换后忘记继续走。有人写成这样while (pA ! pB) { if (pA null) pA headB; if (pB null) pB headA; pA pA.next; pB pB.next; }这段代码的问题在于当 pA 切换到 headB 后紧接着又执行了pA pA.next相当于跳过了 headB 这个节点。正确的逻辑应该是切换或前进二选一而不是先切换再前进。5.2 常见问题速查表问题现象可能原因解决方法返回了错误的相交节点用了值比较而非引用比较改用Java或isPython程序死循环循环条件写成了pA ! null pB ! null改为pA ! pB不相交时返回了非 null指针切换逻辑有误检查切换和前进是否二选一相交节点是头节点时出错空判断或初始化有问题检查 headA/headB 为 null 的处理链表很长时超时用了暴力双重循环改用双指针法或哈希表法5.3 调试技巧打印指针走位如果代码逻辑怎么看都对但结果不对我常用的方法是加打印把每一步指针的位置和值打出来while (pA ! pB) { System.out.println(pA: (pA null ? null : pA.val) , pB: (pB null ? null : pB.val)); pA (pA null) ? headB : pA.next; pB (pB null) ? headA : pB.next; }跑一遍小规模的测试用例看指针走位是否符合预期。这个方法虽然笨但在排查指针类问题时特别有效。我试过好几次打印出来一看就发现是切换逻辑写反了。5.4 测试用例设计建议写完代码后至少用以下几组用例验证两个链表完全不相交长度分别为 3 和 4。两个链表在中间节点相交独立部分长度不同。两个链表从头节点就相交完全重合。其中一个链表为空。两个链表都只有一个节点且不相交。两个链表都只有一个节点且是同一个节点。这六组用例覆盖了绝大多数边界情况跑通之后基本可以放心提交。6. 从这道题延伸出的链表思维6.1 快慢指针与双指针的家族关系相交链表用的双指针和环形链表用的快慢指针其实是同一个家族的不同变体。快慢指针利用的是速度差来检测环相交链表利用的是路程和相等来对齐位置。两者都是通过指针的巧妙走位把空间复杂度压到 O(1)。我建议把这两道题放在一起刷体会一下指针走位这个技巧的通用性。刷完这两道再看链表的中间节点删除倒数第 N 个节点这类题你会发现思路是相通的。6.2 空间换时间与时间换空间的取舍这道题是用数学思维省空间的典型案例。哈希表法是典型的空间换时间双指针法是典型的用逻辑换空间。在实际工程里这两种取舍无处不在。比如在数据库查询优化里加索引就是空间换时间而全表扫描就是时间换空间。在缓存设计里缓存就是空间换时间。理解这道题背后的取舍逻辑比记住代码本身更有价值。6.3 链表题的通用心法刷了这么多链表题我总结出一个心法画图、标长度、定指针。画图是把链表结构画出来标长度是把各段距离标清楚定指针是确定用几个指针、初始位置在哪、移动规则是什么。这三步做完代码基本就是翻译图上的逻辑。相交链表这道题画一个 Y 字形标上 a、b、c 三段长度定两个指针剩下的就是数学推导了。这个心法适用于绝大多数链表题包括反转链表、合并链表、环形检测等等。6.4 面试中的表达技巧如果面试遇到这道题我建议这样组织回答先说出暴力解法的思路展示你有解题方向然后提出哈希表法展示你能快速给出可行解最后主动说我可以优化空间到 O(1)引出双指针法展示你的优化能力。在写双指针法时边写边解释数学推导让面试官看到你不仅会写还理解为什么这样写。这种由浅入深的表达方式比一上来就写最优解更容易让面试官跟上你的思路也更能展示你的思维过程。6.5 代码之外的收获这道题让我意识到一个事情很多算法题的最优解背后都有一个简洁的数学原理。双指针法的 abc 推导快慢指针的相遇定理二分查找的区间收敛都是这样。刷题刷到一定程度你会发现记住的不是代码而是这些数学直觉。这种直觉一旦建立起来遇到新题时你会有一种感觉应该这样解的判断力。这种判断力才是刷题真正的收获。最后分享一个我个人的小习惯每刷完一道有代表性的题我会用一句话把核心思路记在笔记里。相交链表这道题我记的是两指针走对方的路总路程相等则相遇。这句话我到现在都记得遇到类似的指针走位题脑子里会自动跳出这个模式。