打卡刷题到第12天链表双指针这个专题终于轮到两道最经典的题目链表相交和环形链表II。这两道题在LeetCode上分别是160和142难度都标着“中等”但很多人在链表面试里翻车就翻在这两个看似简单的题上。链表相交要找出两个单链表相交的起始节点环形链表II要在一个可能带环的链表中找到环的入口两者都能用双指针优雅解决但理解背后的推导过程才是真正的分水岭。这篇文章把我自己啃这两道题时的思路、推导、C代码和踩坑记录全部整理出来给同样在链表题目里挣扎的朋友一份可以直接参考的笔记。不需要你有很强的算法基础只要会C基本语法、知道链表节点长什么样就能跟着一步步把这两道题的原理和实现吃透。1. 两道题放在一起刷先理清链表题的底层套路1.1 C里链表节点到底长什么样刷题前先把C里链表节点的定义写清楚。LeetCode的模板通常长这样struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };一个节点包含一个整数值val和一个指向下一个节点的指针next。构造函数里的next(nullptr)很关键它保证每个新节点创建出来的时候next一定是空指针不会出现野指针问题。我在本地练习时习惯写一个带默认参数的构造函数调试更方便struct ListNode { int val; ListNode *next; ListNode(int x 0, ListNode *n nullptr) : val(x), next(n) {} };C里的-运算符是“解引用指针并访问成员”的缩写p-next等价于(*p).next。很多新手混淆p-next和p.next区分标准很简单p是指针类型就用-p是结构体实例就用.。链表题里几乎所有操作都发生在节点指针上所以通篇都是-这个在初学阶段非常容易出错。1.2 链表操作的核心判断“指针相等”而不是“值相等”链表相交和环形链表II这两道题共同的核心都落在了指针相等上。链表相交里要找两个链表的交点本质是找第一个“内存地址相同”的节点而不是找第一个“值相同”的节点。两个完全不相交的链表完全可以包含值相等的节点比如两条链表的第三个节点val都等于5但它们不是同一个节点内存地址不同不能算相交。环形链表II里要找环的入口也是要找到那个被重复访问的节点地址而不是等于某个值。很多人在做这两道题时犯的第一个错误就是用nodeA-val nodeB-val去判断相等节点结果在测试用例有重复值时直接返回错误答案。正确写法是nodeA nodeBC里指针相等表示它们指向同一个内存地址这才是链表题目里“相交”“成环”的真正含义。还有一个容易忽略的细节链表题经常需要对头节点做特殊处理比如链表只有一个节点时head-next为空在做快慢指针时如果不提前判断就会越界访问。养成一个习惯拿到链表题先想清楚“空链表”“单节点”“双节点”三种边界情况再开始写代码。2. 链表相交双指针“路程拉平”的推导与代码2.1 题意拆解与两种主流思路链表相交的题面是这样的给定两个单链表的头节点headA和headB如果两个链表相交返回相交的起始节点如果不相交返回nullptr。题目默认这两个链表都没有环。先想一个特别朴素的解法遍历链表A的每一个节点对于每个节点再去遍历链表B看有没有相同地址的节点。这种做法的时间复杂度是O(m*n)一旦链表长度上千跑得很慢面试官基本不会接受。稍微优化一点的做法是把A的所有节点指针存进哈希集合然后遍历B第一个在集合里出现的节点指针就是交点。时间O(mn)空间O(m)。这个思路非常好懂适合笔试时间紧张时先写出来保底。而双指针解法能把空间压缩到O(1)这也是面试官最希望看到的答案。核心思路是两个指针分别从headA和headB出发速度相同但是走到自己那条链表的结尾后不继续停留而是切换到另一条链表的头节点继续走。这样两个指针最终会在交点相遇或者同时到达nullptr。原因是什么呢接下来推导一下。2.2 双指针为什么能相遇路程拉平推导设链表A的长度为m链表B的长度为n两个链表的公共部分长度为c。那么链表A独有的部分长度是m-c链表B独有的部分长度是n-c。两个指针p从headA出发q从headB出发速度都是1步。当p走完链表A走了m步后切换到链表B的头节点继续走。当q走完链表B走了n步后切换到链表A的头节点继续走。注意当它们相遇的时候p在B链上走了m-c步不需要精确到相遇时各自走了多少步只需要证明一个关键结论从p出发算起到它走过B链上不公共的部分再进入公共部分所需的总步数和q走过A链上不公共的部分再进入公共部分所需总步数是相等的。更直观的写法是p从头走到交点需要走(m-c) c m不对因为它先走完A再从B头开始p到达交点时走的总步数是m走完整个A加上从B头到交点的距离(n-c)即m (n - c)。同理q到达交点时走的总步数是n加上从A头到交点的距离(m-c)即n (m - c)。这两个式子展开后都是m n - c完全相等。如果两个链表不相交即c 0那么p走完m n步q也走完n m步它们会同时走到nullptr。这个推导用一句话概括就是速度相同路线总长度被拉平最终一定同时抵达同一个终点。可以想象两个人在两条不同长度的跑道上跑步跑完自己的跑道就换到对方的跑道因为每个人最终都会跑完两条跑道的总长所以会在某个点碰面。2.3 双指针法的C实现与易错细节双指针实现非常短但代码顺序有讲究class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return nullptr; ListNode *p headA, *q headB; while (p ! q) { p p ? p-next : headB; q q ? q-next : headA; } return p; } };关键就在这两行切换逻辑上p p ? p-next : headB; q q ? q-next : headA;p不为空时往前走一步p为空时说明它走完了当前链表切换到另一条链表的头节点。这里要注意p为空后下一轮p指向headB如果headB自身为空其实代码开头已经判断了headB一定非空所以没问题。有一个很容易踩的坑有人会把切换逻辑写成“如果p-next为空就切换”结果在链表末尾判断时机不对少走了一步导致指针在末端和头部之间反复横跳死循环。让指针走到nullptr再切换才是正确写法这样可以保证两条链表总长度的“拉平”过程完整。另一个易错点是在循环体内先判断p-next是否为空试图以此决定是否切换在不相交的两条链表上会因为指针到达末尾的时机不同而出现一个指针停在nullptr等待、另一个还在走的情况虽然有时也能出结果但推导起来不够干净。最简单安全的写法是每次循环先走一步走完判空再决定下一步去哪个头。实测下来这个版本稳。2.4 哈希集合解法作为对照组双指针解法不是唯一解哈希集合解法更适合用来“先做出答案”再在讲解时引出最优解class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* visited; for (ListNode *cur headA; cur; cur cur-next) { visited.insert(cur); } for (ListNode *cur headB; cur; cur cur-next) { if (visited.count(cur)) return cur; } return nullptr; } };这里存的必须是ListNode*而不是int原因前面说过链表相交要看内存地址是否相同。用unordered_set存节点指针本质上是在用哈希表做“这个节点之前有没有见过”的判别。空间复杂度O(m)在内存敏感的场景下不如双指针但在面试里能快速说得清也值得掌握。3. 环形链表II快慢指针判环与入口的数学证明3.1 判断有没有环快慢指针的原理解释环形链表II要解决两件事第一链表里有没有环第二如果有环的入口节点在哪。如果链表无环返回nullptr。判断有没有环最经典的方案是快慢指针也叫Floyd判圈算法。思路非常生活化两个人在环形操场上跑步一个人跑得快一个人跑得慢只要跑道真的围成了圈跑得快的人迟早会从后面追上跑得慢的人。在链表里的落法是slow每次走1步fast每次走2步。如果链表中没有环fast会先到达nullptr此时可以确定无环。如果链表中有环fast和slow一定会相遇且相遇的位置在环内的某个点。为什么一定会相遇而不是跳过去因为每次循环fast相对slow靠近1步不存在跳过的可能所以一定会在某个时刻重合。这里有一个很多人第一次没想通的问题为什么fast一定要走2步而不是3步、4步走3步也能追上但推导过程会复杂得多而且有可能在环长较小的情况下出现越过slow却不相遇的边界问题。走2步时两者的相对速度是1每一轮都在逐步逼近不会跳过数学和代码都最干净。刷题时不必追求花哨的速度组合2步是教科书级的稳妥选择。3.2 找到环入口一段值得手推的公式判定有环之后第二阶段找入口。先设几个量从链表头head到环入口节点的距离为a。从环入口节点出发沿链表前进方向走到第一次相遇点的距离为b。环的周长为r。slow在环内走了多少圈可以先记为0圈fast在环内走了k圈其中k 1因为fast必然比slow多绕了至少一整圈才会追上。第一次相遇时slow走过的总路程是a bfast走过的总路程是a b k*r。由于fast的速度是slow的2倍路程也是2倍a b k*r 2 * (a b)化简得到a b k*r a k*r - b这个式子说明从链表头走到环入口的距离a等于从相遇点继续沿着环走k*r - b步的距离。再看从相遇点走到环入口需要走多少步从相遇点沿前进方向继续走r - b步就能到达环入口。而k*r - b (k-1)*r (r - b)也就是说从相遇点出发走k*r - b步相当于绕了k-1整圈后再走r-b步最终到达的位置同样是环入口。于是Floyd算法的第二阶段就有了依据让一个指针从head重新出发另一个指针留在第一次相遇点两者都每次走1步最终会在环入口相遇。这个结论不是巧合而是上面公式的直接后果。我强烈建议你拿一张纸画一个带头部直线段和环的链表自己把a、b、r标出来一步一步走一遍这个公式就再也忘不掉了。3.3 环形链表II的C实现直接给出完整的C实现class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; do { if (!fast || !fast-next) return nullptr; slow slow-next; fast fast-next-next; } while (slow ! fast); fast head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } };第一阶段的循环用的是do...while这非常关键。因为slow和fast的初始值都是head如果用普通while (slow ! fast)循环体根本进不去直接跳到第二阶段算法就废了。使用do...while先走一步再判断保证第一次比较发生在两个指针都移动之后。判空条件的顺序也很重要先判断!fast再判断!fast-next不能反过来。如果fast本身已经是nullptr访问fast-next会直接触发空指针解引用程序崩溃。用if (!fast || !fast-next)这种写法利用了C逻辑或的短路特性!fast为真时就不会再计算后面的!fast-next安全可靠。第二阶段重新把fast指向head两个指针以同样的速度同步前进根据推导它们会在环入口相遇。这里要注意第二阶段不能用第一阶段的速度差两个指针都必须每次走1步。很多初学改代码时保留fast fast-next-next的写法结果永远追不上输出错误。如果还想用空间换时间哈希集合版本更直接遍历链表把每个节点指针插入unordered_set插入前检查是否已经存在。遇到第一个重复的节点就是环入口。这个方法完全不需要推导笔试抢时间时很实用。4. 实操记录本地调试、常见问题与排查速查表4.1 我在本地怎么编译和调试链表题刷题平台可以直接提交类方法但理解不深时强烈建议本地跑起来观察指针的每一步变化。我自己的环境是VS Code 本地编译器这是个人偏好顺手就行。我在本地调试链表题的固定流程是先写一个main函数手动构造测试链表然后调用题解类的方法。构造链表最常用的辅助函数是“从数组创建链表”ListNode* createList(const vectorint vals) { ListNode dummy(0); ListNode* tail dummy; for (int v : vals) { tail-next new ListNode(v); tail tail-next; } return dummy.next; }构造环形链表时我会先创建整条链再找到指定位置的节点把尾节点的next指向它模拟成环。这里有个细节刷题平台只验证函数逻辑不检查内存泄漏但本地调试时养成释放内存的习惯是好的尤其链表题创建的节点非常多不释放后果很严重。我写了一个freeList函数负责释放注意有环的链表不能简单遍历释放否则会死循环需要先标记或者单独处理。编译时我经常用g -g -o main main.cpp-g选项生成调试信息-o main指定输出文件名。跑出问题时直接gdb ./main在函数入口打上断点用p slow-val查看指针指向的节点值用p slow查看地址。链表题里打印地址比打印值有用得多因为相交和成环判断的是地址。我还习惯在关键位置加临时的cout输出比如输出slow和fast当前指向的节点地址肉眼就能看出两个指针是否在朝预期方向靠近。用VS Code写C时我最常用的导航功能是按住Ctrl点击函数名跳转到定义。这对阅读理解LeetCode模板里的类方法和构造器很有帮助。如果项目引入了预编译头文件比如VS生成的pch.h在本地简单测试时反而会干扰我会新建一个空的控制台项目直接粘贴链表结构体定义不依赖外部预编译头文件减少环境问题干扰。4.2 常见问题与排查速查表链表题的报错往往非常直接不是“段错误”就是“超时”但如果不知道原因排查起来很费劲。我把这两道题最常见的坑整理成一张速查表每一行都是实际踩过或见别人踩过的现象最可能的原因排查思路与正确做法空指针崩溃访问了nullptr的next成员检查所有p-next之前是否有对p的判空程序死循环不退出双指针没有正确切换链表或快慢指针判空条件漏掉打断点观察指针是否在某两个节点之间反复横跳链表相交返回错误节点用val判断相等而不是用指针地址判断改用p q判断指针相等哈希集合版本栈溢出存了int值而不是ListNode*将unordered_setint改为unordered_setListNode*环形链表返回的不是环入口第二阶段没有把指针重置回head确认fast head后两指针同步走do...while写成了while快慢指针初始都在head循环体从未执行使用do...while先移动再比较有环链表释放内存崩溃遍历释放遇到环无法结束先定位环入口再分段处理或忽略释放最值得反复强调的还是判空顺序在fast fast-next-next之前一定要保证fast和fast-next都非空。链表函数的边界处是最容易出幺蛾子的地方宁可多写一个if也不要裸奔访问。4.3 推荐的测试用例设计链表题刷多了会发现很多隐蔽bug不是逻辑想错了而是测试用例没覆盖到位。我自己总结了一套测试用例清单两道题通用空链表head nullptr程序应直接返回nullptr。单节点链表无环时fast-next为空要能正确返回无环。两个节点的链表成环头节点next指向自身入口是头节点。长链表无环确保fast能正常走到nullptr而不是越界。链表相交测试一条链完全包含在另一条里、两条链相交点在中间、两条链尾巴相交。环形链表测试环入口在头节点、在中间、在尾节点附近。每次改完代码先把这些用例都跑一遍比盲目提交等评测靠谱得多。我还习惯把节点地址打印出来跟手动画图的预期对照一旦地址变化和图纸对不上说明代码的执行流和你脑子里想的不一致这时候不要急着猜静下心重新按代码走一遍。5. 刷完这两道题以后我对链表题目的一些沉淀5.1 双指针技巧在链表题里的辐射范围链表相交和环形链表II让我真正理解了双指针在链表问题里的两种经典形态路程拉平和速度差追击。这两种形态能辐射出去解决一大片链表题目判断链表中点快指针走2步慢指针走1步快指针到末尾时慢指针正好在中点这是链表回文判断的基础。找倒数第k个节点快指针先走k步然后两个指针同步走快指针到末尾时慢指针指向倒数第k个。判断链表相交的变体比如两条链表可能带环的情况需要先分别找环入口再做环形判断的复合处理。链表排序里的归并找中点、链表反转里的双指针前后夹击本质也是双指针思路的延伸。可以说双指针是链表题里性价比最高的技巧之一。理解了路程拉平和速度差追赶很多中等难度的链表题就有了统一的思考框架先画出两个指针的运动轨迹再看它们的相遇条件。5.2 链表基本功清单与延伸练习这两道题也暴露出链表基本功的重要性包括链表遍历、链表插入、链表逆置。用C写的时候遍历的模板特别固定for (ListNode *cur head; cur; cur cur-next) { // 处理当前节点 }插入操作要注意先连后断先把新节点的next指向后继节点再让前驱节点的next指向新节点。反过来的话前驱先断开后继节点就找不到了。链表逆置同理需要用一个prev指针保存前驱next指针保存后继防止断链后丢失后续节点。这些基础操作练熟之后再做相交和环形链表的题目会发现轻松很多。如果想进一步巩固可以继续挑战几个经典延伸题判断回文链表、删除链表的倒数第N个节点、排序链表、合并K个升序链表。它们都会用到本文提到的双指针思路或链表基础操作。我在打卡记录里把这些题放在链表专题的后续清单里一道一道啃完整个链表专题的骨架就搭起来了。说回这两道题本身第二次刷的时候我已经能不看推导直接写出双指针代码但心里清楚真正值钱的是那个能自己推导、能向别人讲清楚的过程。我第一次看懂环形链表II的推导花了快一个小时画了三四张图但画通之后代码就再也忘不掉了。如果你也卡在链表题别急着背代码先拿张纸把指针的移动轨迹画出来这一步做扎实了后面会顺利很多。