1. 一道题看出链表基本功相交链表到底在考什么我最早在“代码随想录”里刷到“160. 相交链表”时第一反应是这题挺简单的结果第一版代码就翻车了。不是因为没读过题而是把“相交”理解成了“值相等”。这个误区太常见了后面我会专门说。单说这道题能带给你的东西绝对超过一道普通算法题的量链表遍历、指针移动、循环终止条件、时间和空间复杂度取舍全都在这里了。比如你可以在A链表里先走一遍同时把节点地址记下来然后去B链表里看有没有重复的这就是哈希表思路也可以耍点小聪明让两个指针在链路上绕一圈最终神奇地“接上头”这就是双指针思路。两种方式各有各的适用场景但面试里最被认可的往往是空间复杂度更低的那个。题目本身不复杂给两个单链表链表的头节点分别是 headA 和 headB如果两个链表在某个节点开始共享同一段内存就返回这个共享节点的指针如果没有任何公共节点就返回空指针。这里的“共享同一段内存”是至关重要的前提它意味着两个链表如果相交那么从相交点开始后面所有节点都是同一个地址而不是恰好值相同。用生活里的例子说两条马路从某个路口开始完全汇成一条路之后的路况、路灯、摄像头全是同一套这才是“相交”。如果只是路边电线杆等高所以看起来一样不算。理解这个前提之后代码会不会写对基本就靠边界情况了。这个题目在面试里出现的频率很高而且经常作为后续题目的铺垫。你把它吃透了再去碰环形链表、找链表中点、合并有序链表会明显顺手很多。因为链表题的解题手感主要就来自对“指针移动”的掌控力什么时候该停、什么时候该换路、什么时候会死循环这些判断力不是背题背出来的是反复调试调出来的。接下来我就把三条主流思路逐一拆开讲清楚它们的取舍和实现细节。2. 为什么暴力法不行从哈希表到双指针的思路演进2.1 暴力枚举和哈希表能解但不够优雅最容易想到的做法就是用嵌套循环。对 headA 中的每个节点遍历整个 headB看看有没有节点和它指向同一个地址。空间复杂度是 O(1)但时间复杂度是 O(m*n)。m 和 n 分别是两条链表的长度一旦链表长度破万基本就等着超时。这种写法在笔试里能不能过看数据范围在面试里却几乎没法拿出来聊因为面试官马上会追问“太慢优化一下”。优化方向很直觉既然 A 链表的节点可能被反复遍历那就先存起来。用一张哈希表记录 headA 经过的所有节点指针然后遍历 headB逐个检查当前节点是否在哈希表中。第一次命中的节点就是相交节点。时间复杂度降到 O(mn)因为两条链表各遍历了一遍哈希表增删查都是平均 O(1)。但代价是空间复杂度变成 O(m)因为要把较长的一条链表所有节点都存进去。哈希表解法是很多教科书里的标准答案也是大家最容易写出来的版本但我个人认为它不是最优解原因不是它没法用而是它有更轻量、更体现“算法直觉”的版本。面试如果只写哈希表大概率会被继续追问一句“能不能把空间复杂度也降到 O(1)”这道题真正让人眼前一亮的地方就是那个空间 O(1) 的双指针解法。理解它需要一点逻辑铺垫两个指针分别从 A、B 出发当一条链走完时让这个指针跑到另一条链的头部继续走两个指针最终会同时走到相交点。看起来像变魔术实际上数学上非常严谨。后面我会解释为什么能相遇这里先给结论如果两条链表相交那两个指针会“殊途同归”如果两条链表完全不相交那两个指针会同时走向空指针。无论是哪种情况循环都不会卡死这个特性让双指针解法成为这道题的最佳解法。2.2 双指针的相遇逻辑用一段路程差弥合长度差为什么双指针能对设链表 A 在相交前的长度为 a链表 B 在相交前的长度为 b公共部分长度为 c。两个指针同时出发速度相同走过的节点数也相同。指针 pA 走完 A 的长度 ac 后会切到 headB 上接着走指针 pB 走完 B 的长度 bc 后会切到 headA 上接着走。它们在各自完成“本链 对方链”的行走后分别走过的总节点数都是 acb 和 bca完全相等。而这条路线的总长度等于 abc也就是两条链表相连成一个环之后恰好把相交点包含在内。两个速度一样的人走同一条路自然会在同一个时间、同一个点相遇。用例子验证A 链表为 1-2-3-4-5B 链表为 9-8-3-4-5相交点是 3。此时 a2b2c3。pA 走完 1,2,3,4,5 后切到 B 的 9继续走 9,8pB 走完 9,8,3,4,5 后切到 A 的 1继续走 1,2。最终它们都在第三个节点“3”相遇。有意思的是即使 a 和 b 差距很大这个“差值”也会在切换路径后被抵消因为慢速的那个会提前进入对方的链表走得更远一点。这一套逻辑让双指针解法既不需要知道长度也不需要额外存储只靠指针的移动就解决问题。2.3 长度差法直观但需要额外一次遍历除了双指针还有另一种容易理解的解法长度差法。先分别遍历两条链表数出长度 lenA 和 lenB。让更长的链表先走 lenA-lenB 的差值步假设结果是正数这样两个指针就处在同一起跑线之后同步前进第一个位置相同的节点就是相交点。这种思路的代码比双指针长一点但逻辑更“按部就班”特别适合口头解释给面试官听。空间复杂度同样是 O(1)时间复杂度是 O(mn)因为要分别遍历一次取长度然后可能再遍历一次找交点。我在刷“代码随想录”的时候明显感觉到它推荐双指针解法是有道理的长度差法需要先知道两个链表的长度这有赖于“链表有尾”的前提而双指针连长度都不用算代码也更简洁。面试时如果时间不够双指针版本甚至可以三五行搞定。不过话说回来长度差法的代码更不容易写错因为它的步骤是线性的先量长度再对齐最后找交点。我自己准备面试的时候会把这两种方法都背熟因为同一个题很难保证面试官就喜欢听某一种思路。他要是先问我“你怎么找两条链表的长度差”我就顺着给长度差法他要是问“能不能再优化”我就顺势切换到双指针。这种一鱼两吃的准备方式每次面试效果都不错。3. 完整代码实现把思路落到 C / Python / Java3.1 C 双指针实现贴合代码随想录的写法如果你看过“代码随想录”里链表篇的代码风格会习惯它定义 ListNode 结构体时用得很顺手例如struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };然后 160 题主函数可以这样写class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *curA headA; ListNode *curB headB; while (curA ! curB) { curA curA ? curA-next : headB; curB curB ? curB-next : headA; } return curA; } };有些同学第一次看到这段代码会愣一下因为curA curA ? curA-next : headB这个写法有点绕。拆开看就是如果 curA 不是空就往前移动一步如果 curA 已经走到空说明 A 链表走完了就跳去 headB 从头走。curB 同理。这个写法巧妙地利用了“空指针”作为“换路”的信号不需要额外维护一个标志位。循环结束有两种情况两个指针在相交点相遇或者两个指针都变成空指针代表没有交点。无论哪种返回的都是“第一对相等指针”代码自然成立。如果觉得三目运算符影响可读性完全可以改成 if 语句效果一样while (curA ! curB) { curA (curA ! nullptr) ? curA-next : headB; curB (curB ! nullptr) ? curB-next : headA; }3.2 Python 和 Java 版本换语言思路不变Python 的写法最简洁也是我平时做算法题时最常用的版本class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: p, q headA, headB while p is not q: p p.next if p else headB q q.next if q else headA return p注意这里判断用的是is not不是!。因为 Python 里两个节点的“值相等”不代表“是同一个对象”。ListNode 没有重写__eq__方法的情况下默认判断的是内存地址但使用is能更加明确表达“我们要比较的是对象身份”。如果题目给的链表节点类来自 LeetCode那!其实也能凑合但写is更稳妥也更能体现你清楚“相交”的本质是同一个对象。Java 版本的代码同样不难public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p headA; ListNode q headB; while (p ! q) { p (p null) ? headB : p.next; q (q null) ? headA : q.next; } return p; } }Java 里没有is这样的身份运算符直接用!和比较对象引用正好符合我们的需求。三段代码的核心思想一模一样两个指针走完自己的路再去走对方的路最终殊途同归。刷题的时候不用刻意背三种语言掌握一种另外两种自然能默写出来。3.3 边界条件什么时候最容易翻车链表题最大的坑永远是边界。这里列几个我当初踩过、也常见别人踩的坑。第一两个链表都为空。这时循环条件curA ! curB检查的是两个空指针二者相等根本不进入循环直接返回空指针结果正确。第二两个链表从头就相交。比如两个链表完全一样每个节点地址相同那 curA 和 curB 一开始就相等返回 headA结果正确。第三两个链表无交点。双指针会把两条链表彻底走完最后同时为 null 退出循环返回 null。关键是这种无交点情况会不会死循环答案是不会因为走完mn步之后两个指针都会停在空上循环条件不成立。这一点在 4.1 里会再算一遍。还有一类隐蔽错误是拿“值”比较。假如链表节点值恰好有重复而两个链表并没有共享节点curA-val curB-val可能会误报。我第一次写这个题就是从头到尾比 val然后看起来部分测试能过但一旦两个链表在数值存在相同但地址不同时直接得出错误答案。正确做法是比较指针本身C 里比较的是 ListNode* 的地址Java 和 Python 里比较的是对象引用而不是 val 字段。这也是这类“引用类题目”的通用护身符。4. 模拟运行与复杂度不仅要知道“能过”还得知道“为什么能过”4.1 无交点情况的数学验证很多文章只讲双指针在有交点时如何相遇却没回答“万一没交点呢”。这里补上。设链表 A 长度为 L1链表 B 长度为 L2。pA 在 A 上走完 L1 步后跳到 B再走 L2 步后到空pB 在 B 上走完 L2 步后跳到 A再走 L1 步后到空。总的行走步数pA 是 L1L2pB 是 L2L1。完全相等。也就是说两个指针会在同一时刻走到空指针循环条件while (curA ! curB)在看到两个 null 时自动不成立于是返回空。这个过程和有没有交点无关只是一个精确的“步数同步”机制。有交点的时候两个指针会在某个更早的节点相遇总步数小于等于 L1L2。无交点的时候它们会在第 L1L2 步相遇而这个“相遇点”是空。这个设计非常精妙不管结果如何循环都能终止而且不会把逻辑写复杂。面试里如果能主动说出这一层“环状行走”的数学依据绝对是个加分点。4.2 时间复杂度、空间复杂度与 LeetCode 上的实际体验双指针解法的时间复杂度是 O(mn)。这里的 m、n 是两个链表长度每个指针最多走 mn 步两个指针合计最多走 2(mn) 步常数 2 不影响复杂度。空间复杂度是 O(1)因为只用了两个辅助指针。相比之下哈希表法的空间复杂度是 O(max(m,n))在数据量大的场景下容易吃到内存限制。在 LeetCode 的测试用例里双指针运行时间通常能击败绝大多数提交因为链表操作本身很快而且空间占用小。我实测过几次当 mn100000 左右双指针解法耗时基本稳定在几十毫秒内哈希表解法可能耗时会稍高一些主要花在哈希表的插入和查询上即便理论复杂度一样常数因子也偏大。所以从工程角度讲双指针不只是面试的“漂亮解法”实际处理嵌入式链表、C 内存受限场景时空间 O(1) 的优势也很明显。后面第 6 节我会细说这种思路在代码里的延伸价值。4.3 模拟一遍用表格看指针移动为了方便理解我拿一组简单的链表模拟双指针移动。假设 A 链表节点分别是 A1、A2、C1、C2B 链表节点分别是 B1、B2、B3、C1、C2相交点是 C1。设 pA 从 A1 出发pB 从 B1 出发每一步同步前进。表格里每一步两个指针所在节点步数pA 指向pB 指向说明1A1B1无交点继续2A2B2无交点继续3C1B3pA 先进入公共段4C2C1pB 进入公共段5空C2pA 走完 A切到 headB6B1空pB 走完 B切到 headA7B2A1两人都在对方链表上走8B3A2继续走9C1C1相遇返回可以看出它们在步数 9 时于相交点 C1 相遇。如果纸上画一下会发现 pA 和 pB 的路径正好形成一个类似“8”字的回路而公共段是那个交叉点。很多人第一次看到这个表会问为什么 pA 先走到 C1pB 还没到但它们不会在 C1 相遇因为循环条件是“每一步都检查”不是“等走到同一个节点再碰头”后到的 pB 需要再走两步才能到 C1而此时 pA 已经过了 C1 并走到空指针切换到了 B 链。这种错位正是双指针能消除长度差的原因它让先跑完的指针去对方链路上“补长度”最终两个指针跑过的总步数相同并且总能在同一时刻抵达同一个点。5. 刷题过程中最常见的 5 个坑和排查技巧5.1 空链表和单节点链表很多人会想当然地把 head 为空的情况放在循环外处理其实没必要。上面代码已经覆盖了。如果 headA 为空而 headB 非空循环第一次检查的就是null和headB显然不等进入循环后 pA 会变成 headBpB 也按照pB ? pB-next : headA移动最终也能走完并返回 null。这个行为正确只是不够直观。我的习惯是写链表题前先问自己一句这个解法在“空链表”、“单节点链表”、“全等链表”、“无交点链表”这四种情况下分别会怎样如果都能自洽大概率没问题。5.2 整条链表从头相交当 headA 和 headB 指向同一个节点时循环不会执行直接返回 headA。这正确。但有些同学会错误地把这种情况排除在外认为“相交必须发生在两个节点之后”然后强行让指针先各走一步导致结果变成第一个节点的 next。这个坏习惯多半是从“找第一个交点”的语义里带出来的但实际上两个链表可以从头节点就开始共享比如 A 和 B 都是同一个链表的别名。代码不需要特殊处理。5.3 用值相等判断相交这个坑我在开头就提过值得再强调一次。链表相交是“地址相交”不是“值相交”。假设 A 链表是 1-2-3B 链表也是 1-2-3但是两组节点是在内存中分别创建的那么它们的地址完全不相同不存在相交节点。用值相等去判断会返回第一个节点直接判错。在 C 中判断指针是否相等比较的是指针变量本身而不是curA-val。在 Python 中比较对象用is在 Java 中比较引用用这些都是硬规矩。5.4 指针走到空就立刻切换有同学会写成curA curA-next然后发现空指针崩溃于是加个 if但 if 的条件写成了while (curA-next)导致最后一个节点直接跳过终点永远是倒数第二个节点。这里要理清楚“当前节点为空”才需要换路而不是“下一个节点为空”就换路。判断时必须用curA nullptr然后让 curA 指向另一条链表的 head。如果写成curA-next nullptr才换那等 curA 走到最后一个节点时还没有换路下一步你的 curA 会变成空指针而空指针没有 next再次访问就会崩溃。正确的语义是等 curA 已经为空了说明这条链表的路走完了此时把它安放到另一条链表的起点。顺序不能反。5.5 无交点链表跑不完有些人担心两个不相交的链表会让循环无限跳转。根据 4.1 的数学验证不会。但如果你把切换条件写错比如让 pA 从 headB 走完后再次跳回 headA而不是让 pA 在 A 走完后去 headB且 pB 在 B 走完后去 headA就可能出现两个指针各自在自己链表里打转永远碰不到。最直接的排查方法加一个计数器如果步数超过 L1L2就说明写错了。或者干脆在本地跑几个极端用例比如 A 长度 100B 长度 1确保结果和样例一致。我每次刷链表题都会打印最终返回节点的val和一个内存地址值用肉眼确认它确实属于公共段。6. 刷完这道题之后双指针思想还能往哪走我个人非常喜欢“相交链表”的原因不只是它作为一道面试题很经典而是它引出了一种思维模式当两条路径长度不一致时可以让执行者交换路径来“对齐距离”。这种思维在链表相关题目里反复出现。例如寻找链表的倒数第 k 个节点让一个指针先走 k 步另一个再跟上寻找链表的中点一个快指针走两步一个慢指针走一步。它们本质上都是“用步数差来定位”。再比如环形链表 II要求找环的入口节点它的一条经典解法也是双指针其中数学推导和“相交链表”的推导一脉相承两个指针在环内相遇后让一个指针回到头节点然后两个指针再同步走最终会在入口相遇。如果能把相交链表这一题的指针切换逻辑理解透彻再去学环形链表会快很多。具体到工程应用嵌入式或者驱动代码里经常出现链表结构比如 Linux 内核里的 list_head 设计用偏移量计算宿主结构体本身就依赖地址操作。在内存受限环境中你要判断两个集合是否有重合区域或者两条设备链表是否有公共节点双指针的思路比哈希表更省资源因为它不需要额外的分配和释放。即便语言层面没有内置链表结构只要你能自己写出节点结构这套算法就能原样迁移。所以这道题刷完后我习惯了在遇到“两条路径”“两个序列”“双数组”类问题时多问一句能否用双指针做到 O(1) 空间这种条件反射就是靠刷这种经典题养出来的。关于代码随想录我自己的体会是它很适合用来建立知识框架。“相交链表”在链表章节里看似独立但它和“两个链表的公共子序列”“链表的成环”等概念是互相关联的。最好的刷题方式不是照着代码默写而是先把思路理解了再自己动手实现然后用三五个测试用例验证最后再回头对比参考代码。我在实际写这道题时一开始把双指针的换路条件写反了结果在无交点链表上死循环后来把两个指针的位置在纸上画清楚才真正记住谁走完谁换路换到另一条链表的起点。这个“画图模拟”的习惯才是刷链表题不困的核心秘诀。如果以后再有人问我“相交链表怎么做”我不会直接扔代码而是先问一句“你知道两个链表相交意味着它们的尾部一定相同吗”从这个问题出发自然就能引出长度差法和双指针法。代码只是手段把链表结构在脑子里转起来才是本事。希望这篇总结也能帮你把这道题真正装进长期记忆里下次在白板前面写这道题时三分钟能说清思路两分钟能写完代码那就真的到位了。