刷题打卡进行到第12天今天卡的是链表双指针里的两道经典题链表相交和环形链表II。LeetCode上分别对应160和142一道是中等难度的几何构造题一道是中等难度的推导题但它们指向同一个核心能力——用两个指针在链表上做“轨迹规划”然后通过指针相遇的规律反推节点位置。这两道题不像反转链表那样背完模板就能写它们的解法需要真正理解所以我把推导过程、C实现、调试时踩过的坑、以及能延伸出来的变形题都整理在这篇打卡记录里适合正在按专题刷链表、且已经写过基本遍历和增删操作的读者。1. 两道题先别急着敲代码把模型想清楚很多人在LeetCode上看到链表题第一反应是打开编辑器直接写循环。我建议先反过来花十分钟把两个题目背后的指针模型画在纸上写代码时基本一遍就过。这一节把两道题的数学模型和解题思路讲透。1.1 链表相交问题到底在问什么链表相交这道题给定两个链表头headA和headB要求返回两个链表相交的起始节点如果完全不相交则返回nullptr。注意“相交”在链表里指的是两个指针指向同一个节点对象也就是两个节点在内存中的地址相同而不是两个节点的val值相等。链表A可能是 1-2-3-4-5链表B可能是 9-4-5这里的4和5不是两个分别存在的节点而是同一个节点被两条链同时引用。这个前提搞清楚后面的双指针法才说得通。最直接的解法是哈希表遍历链表A把每个节点指针存进unordered_set再遍历链表B第一个能在set里找到的节点就是交点。时间O(nm)空间O(n)。这个解法能过但面试里更希望看到空间O(1)的双指针法。双指针的思路非常对称pA从headA出发pB从headB出发每次各走一步pA走完链表A之后跳到headB继续走pB走完链表B之后跳到headA继续走。两个指针最终要么在相交节点相遇要么同时走到nullptr返回空。为什么这个做法成立假设交点前链表A的长度是a链表B的长度是b交点后公共部分长度是l。pA完整走过的路径是a l bpB完整走过的路径是b l a二者的路径长度完全相等所以当它们各自走完自己的路径时会同时停在交点处。如果两条链表根本没有交点那pA走完AB的长度后落在nullptrpB走完BA的长度后也落在nullptr二者同时为nullptr循环退出返回nullptr。这个“同时性”是整个解法的灵魂也是判断代码写没写对的关键。1.2 环形链表II三步拆解环形链表II的题面比第一问多了一点点要求不仅要判断链表有没有环还要返回入环的第一个节点。LeetCode 142在原题里算是环形链表I的加强版判断有环用快慢指针已经够用但找到入口节点需要做一次简单的数学推导。快慢指针判断环的方法很简单slow每次走一步fast每次走两步如果fast在某个时刻等于slow说明链表有环如果fast走到了nullptr说明无环。难的是找到环入口。这里定义一个标准的符号体系会很方便设链表头到环入口的距离为a环入口到快慢指针第一次相遇点的距离为b相遇点继续沿链表方向走回环入口的距离为c那么环的长度就是b c。slow从head走到相遇点的总路程是a b。fast从head走到相遇点的总路程是a b再加若干圈环如果快指针在环内多绕了n圈那么fast总路程是a n * (b c) b这里其实可以拆成a (n * (b c)) b也就是a加上n个整环再加上入口到相遇点b。由于fast速度是slow的两倍就有2 * (a b) a n * (b c) b化简之后得到a (n - 1) * (b c) c。这个式子说明一个很漂亮的事实从头节点出发走a步能到环入口从相遇点出发绕(n - 1)圈再走c步也能到环入口而c恰好是相遇点到环入口的距离。所以相遇之后把一个指针放回head另一个留在相遇点两个指针每次各走一步它们一定会在环入口相遇。还有一个经常被问到的问题为什么slow在环内走不完一圈就会被fast追上因为fast相对slow的速度是每步多走一格而两者在环内的初始距离小于环长所以在slow绕完一圈之前fast一定能把这个距离差追平。这个直觉可以帮助省掉很多不必要的担心。2. 链表相交的C实现与细节剖析模型清楚了代码其实很短。但短代码里的细节很多我把自己最开始写错的地方重点标出来尤其是“什么时候跳到另一条链表”这个问题如果不小心会在边界样例上绕圈子。2.1 双指针循环实现与逐行解读链表相交双指针的标准C写法如下struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA nullptr || headB nullptr) { return nullptr; } ListNode *pA headA; ListNode *pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; }while循环退出条件只有两个pA和pB指向同一个节点说明找到交点pA和pB同时为nullptr说明走到两条链的末尾链表不相交。注意这里判断跳转用的条件是pA nullptr不是在pA-next nullptr时跳转。我最早写的时候习惯漏掉pA本身为空的判断把三元条件写成pA-next nullptr ? headB : pA-next结果在一个链长度为0的测试用例里直接崩溃。空指针本身也是一种状态它表示“已经走完了当前这条链表”必须在这种状态下才切换到另一条链表。这个解法的时间复杂度是O(m n)两个指针最多各走两遍两条链表空间复杂度O(1)。提交的运行时间在LeetCode上属于第一梯队。顺便说一句如果在面试中被问“能不能用哈希表”可以提哈希表写法但要把空间复杂度说清楚然后主动给出双指针的优化方案这是面试官比较愿意听到的答卷。2.2 哈希表的C写法与对比哈希表解法虽然空间复杂度不是最优但逻辑更直观适合作为双指针的对照。C里需要记住一个关键点unordered_set的模板参数应该是ListNode*也就是存节点的地址而不是int。C的unordered_set 默认会对int值做哈希但链表中两个节点即使val相同也不是同一个节点所以必须用指针作为key。ListNode *getIntersectionNodeHash(ListNode *headA, ListNode *headB) { std::unordered_setListNode* seen; while (headA ! nullptr) { seen.insert(headA); headA headA-next; } while (headB ! nullptr) { if (seen.find(headB) ! seen.end()) { return headB; } headB headB-next; } return nullptr; }这里用seen.find(headB) ! seen.end()判断是否存在不要用seen.count(headB)的返回值当布尔值虽然也能用但find的语义更明确。两种方法我都提交过哈希表在数据量很小时可能因为没有指针校准的额外遍历而更快一点但双指针的O(1)空间优势在面试场景里更重要。2.3 本地构造相交链表的实测过程为了验证算法我在本地写了一个main函数手动构造两条共享尾部的链表。构造方式很关键先把公共部分创建出来再分别让两条链的尾节点指向它。核心代码片段如下int main() { ListNode *common new ListNode(8); common-next new ListNode(10); ListNode *headA new ListNode(1); headA-next new ListNode(2); headA-next-next common; ListNode *headB new ListNode(3); headB-next new ListNode(4); headB-next-next new ListNode(5); headB-next-next-next common; ListNode *node getIntersectionNode(headA, headB); if (node ! nullptr) { std::cout 相交节点值: node-val std::endl; } else { std::cout 不相交 std::endl; } // 这里没有释放 common 和两个头节点本地调试可以忽略 return 0; }输出结果应该是“相交节点值: 8”。这个测试用例模拟的就是标准题目里的链表A和B公共部分是common和它后面的节点。需要提醒的是因为两条链表共享了节点如果后面写释放逻辑绝不能分别delete headA和headB否则common会被释放两次这是本地测试里一个很容易翻车的点。3. 环形链表II的C实现与数学推导环形链表II的代码相比链表相交只长了几行但它的难点在于“为什么相遇之后这样走就能找到入口”。这一节把代码和推导绑在一起写建议对着gdb边看变量边理解。3.1 快慢指针与入口查找的完整实现ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return nullptr; } ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode *index1 head; ListNode *index2 fast; while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index1; } } return nullptr; }这个写法先把空链表和只有一个节点的链表直接排除避免后面while循环里访问fast-next-next时崩掉。快指针每次走两步所以循环条件必须同时判断fast本身和fast-next不为空少一个判断都会在链长为奇数的无环链表上出错。有环时slow和fast一定会在某个节点相遇相遇后把index1放在headindex2放在相遇点fast然后同步走第一次index1等于index2的节点就是环入口。我在第一次做这道题的时候试着用哈希表存访问过的节点也能过但理解不了“入口为什么能由相遇点推出来”。后来把a、b、c的公式抄在纸上画了三遍才真正接受这个结论。代码本身不是问题推导才是。3.2 从相遇点到入口的距离公式推导重复一遍核心推导设head到环入口的距离为a环入口到快慢指针相遇点的距离为b相遇点继续走到环入口的距离为c环长是b c。slow从head到相遇点走了a b。fast从head到相遇点除了走完a b之外还因为比slow快在环里多绕了若干圈设绕了n圈那么fast总路程是a b n * (b c)。等等这里有一个需要辨析的地方fast从入口到相遇点这一段如果它是第一次经过那么路程就是b如果它已经绕了n圈其实总路程应该是a (n * (b c)) b这个式子等价于a b n * (b c)。因为2 * (a b) a b n * (b c)化简后a b n * (b c)进一步得到a n * (b c) - b (n - 1) * (b c) c。所以从头节点出发走a步到入口与从相遇点出发先绕(n - 1)圈再走c步到入口两个动作需要的步数相同。这就是为什么一个指针放在head一个指针放在相遇点同步每次走一步最终能在入口碰上。需要注意的是n不一定等于1当链表很长而环很短时fast可能已经绕了好几圈但无论n是几公式都成立。为了验证这个结论我构造过一条head到入口距离较长、环很短的测试链手动演算发现n大于1的情况确实存在代码依然正确。所以这道题的代码只要按公式写不需要关心n实际是多少。3.3 边界情况与复杂度分析环形链表II的边界情况比链表相交多一些链表为空或只有一个节点不可能成环直接返回nullptr。整个链表就是一个环入环点在heada 0index1从head出发index2从相遇点出发第一次相遇就在head返回head逻辑正确。链表成环但入口不在head这是最常见的场景前面的公式推导已经覆盖。快慢指针相遇后index1和index2如果一直不相遇这说明代码里的快慢指针遍历逻辑写错了正常情况下有环必定相遇。时间复杂度是O(n)因为快慢指针第一阶段走的总步数不会超过链表节点数的常数倍第二阶段index1和index2走的距离也不超过链表长度空间复杂度是O(1)。这个复杂度级别和LeetCode官方题解一致本地测试跑100万个节点的链表也没有压力。4. 实测过程中的坑和调试方法算法题真正花时间的不是写出正确解而是面对报错和异常时怎么定位。我把这两天实际遇到的编译问题、死循环问题和调试工具使用经验整理出来这部分在很多题解里基本不会写。4.1 C的-运算符与常见编译错误链表节点的成员是val和next但节点通常以ListNode*形式出现所以访问成员必须用-而不是点号。比如ListNode *p访问下一个节点要写p-next如果你写p.next编译器会报错“left of .next must have class/struct/union”。我第一次上手C链表时这个错误几乎每道题都会犯一次后来就养成习惯看到指针类型就默认用-。还有一个对新手比较常见的坑是混淆“节点的next为空”和“指针本身为空”。在链表题里p nullptr和p-next nullptr是两个完全不同的条件。前者表示当前指针不指向任何节点后者表示当前节点存在但它的后继节点不存在。环形链表II的循环条件里判断fast-next ! nullptr就是为了保证fast可以安全地再往前走两步如果你少写这个条件当fast恰好是尾节点时访问fast-next-next就会触发segment fault。这种错误在本地用gdb看栈能很快找到但在LeetCode上只会显示一个Runtime Error所以写代码时就要把判空写完整。4.2 本地编译调试cpp -g -o 到底怎么用我通常会用命令行编译本地刷题代码链表题需要看变量状态时特别方便。以Linux/macOS环境为例编译命令是cpp 文件名.cpp -g -o 可执行文件名或者更常见的写法用gg -g 文件名.cpp -o 可执行文件名这里的-g表示生成调试信息加了它之后gdb才能显示源码行号和变量值-o指定输出文件名。有的环境里cpp命令就是C编译器入口有的环境里cpp是C预处理器如果你发现cpp命令不识别切换成g或clang即可。编译成功后可以运行gdb ./可执行文件名然后在gdb里设置断点比如在detectCycle的第一个while循环处break 21 run next print slow-val print fast-val这样能看到fast每轮走两步时跳过了哪些节点环形链表里能不能追上slow。我调试环形链表时最喜欢打印节点值但这里有个小教训如果链表很长或者成环print会输出很多内容而且光看值无法确定是不是绕圈。更好用的办法是打印节点地址比如print slow和print fast两个十六进制地址相等就说明指针指向同一个节点对象这是判断相交和成环的铁证。4.3 在VS Code里快速导航到函数定义很多人问“vscode怎么导航到cpp函数定义”其实很简单。安装微软的C/C扩展之后在函数名上按F12可以直接跳到定义ShiftF12可以查看所有引用或者按住Ctrl键再用鼠标点击函数名也能跳转。链表题里最常见的用法是单击ListNode结构体定义跳转到头文件确认成员变量名字在长文件里想回到刷题主函数按一下Ctrl-就能回到上一个位置。如果按F12没反应多半是IntelliSense没有索引当前文件。可以按CtrlShiftP输入“C/C: Reset IntelliSense Database”重建索引。另外本地单文件刷题建议不要开预编译头单cpp文件编译本来就很快开启预编译头反而会在第一次编译时生成很多中间文件报错也更绕。Visual Studio用户如果遇到奇怪的“预编译头文件不是此编译单元的第一个文件”之类的报错直接关掉预编译头选项就好。4.4 调试链表题的两个常用辅助函数链表题没有内置的打印方法自己写一个printList会很省事void printList(ListNode *head, int limit 10) { ListNode *cur head; int cnt 0; while (cur ! nullptr cnt limit) { std::cout cur-val - ; cur cur-next; cnt; } std::cout null std::endl; }这个函数我在刷链表基础题时几乎每次都copy。limit参数很有必要万一链表里有环printList不会无限跑下去到第10个节点就自动停方便观察结构。还有一个小技巧在环形链表题里可以直接把limit设为3观察前几个节点的值配合打印节点地址比纯打印值更可靠。4.5 常见问题速查表这里我整理了一份链表双指针题的常见问题速查表都是我实际遇到或者帮别人远程debug时见过的现象原因解决办法运行时报错“member access within null pointer”在空指针上访问了-next在循环条件里先判空或者用三元表达式区分指针为空的情况相交链表在本地死循环节点走到nullptr后没有切换到另一条链表一直原地停留检查跳转条件确实要用pA nullptr而不是pA-next nullptr环形链表输出“不相交”但实际有环快指针循环条件写错导致提前退出确认fast ! nullptr fast-next ! nullptr齐全两个链表节点值相同被判成交点但逻辑不对用val相等判断指针相等一律用指针地址比较链表相交只认节点对象相同本地构造测试链表后delete两次导致崩溃两条链表共享公共节点重复释放简单调试不释放或统一用一个释放函数标记访问过的节点这张表里的第一条是我自己印象最深的因为它在链表题里是最隐蔽的。很多报错信息不会告诉你是哪一行只告诉你空指针访问这时候在gdb里输入backtrace看调用栈找到具体行然后检查是不是某个节点没有判空就去访问next了。5. 面试延伸从这两道题能带出哪些变形题链表相交和环形链表II本身是两道题但它们覆盖的技巧可以扩展出一大串高频面试题。如果你时间有限把这一节提到的变形题全部掌握链表这部分基本就稳了。5.1 单链表逆置是必然要会的核心操作链表逆置是每场面试几乎必考的基础题LeetCode 206。它的迭代写法是双指针思路在链表操作里最经典的应用三个指针prev、cur、next协同工作每轮先把cur-next保存到next再把cur-next指向prev然后prev和cur各自前进。ListNode *reverseList(ListNode *head) { ListNode *prev nullptr; ListNode *cur head; while (cur ! nullptr) { ListNode *next cur-next; cur-next prev; prev cur; cur next; } return prev; }这个操作一旦熟练后面的K个一组反转链表、两两交换相邻节点这类题就容易很多。可以看到链表相交和环形链表里的指针跳转技巧和逆置其实是一个家族都是在链表节点间重新规划指针的走向所以刷题时建议把这几个题目连着刷。5.2 循环单链表的理解环形链表II本质上就是在和“循环单链表”打交道。循环单链表的特点是尾节点的next指向头节点链表的最后一个节点不是nullptr而是回到head或者环入口之前的某个节点。很多教材里的约瑟夫环问题就是用循环单链表模拟的面试官如果顺着环形链表聊很可能会问“如果我现在用循环链表存数据怎么判断它是否异常成环”这时候你把快慢指针的解法说出来再补充一句“还需要找到入口才能修复”基本能对上。5.3 基于链表的集合差集等综合题数据结构的课程设计里有一道常见题用链表表示两个集合求差集。给定两个有序链表A和B求A中有而B中没有的节点。思路是双指针同时遍历两个链表因为链表有序所以可以比较两个当前节点的val值小的必然不在另一个集合里直接收集并移动指针值相等的说明两边都有跳过值大的说明另一个链表后续可能还有更小的先移动相对较小的指针。这段逻辑写起来很像归并排序的合并过程但它考察的是“链表指针的移动一致性”。很多新手会在相等时只移动一个指针导致死循环这正好用得上今天调试链表相交时养成的“指针同步推进”习惯。5.4 C链表在实际项目里的存在感另外提一句热搜词里出现的“嵌入式链表代码示例”。嵌入式内核里最常见的链表不是这种单链表而是双向循环链表通常把链表节点内嵌进结构体再用container_of宏从链表节点反推出宿主结构体。刷题刷的是单链表的指针操作真正做事时还需要理解双向链表、头节点哨兵、内存分配与释放这些工程化内容。不过链表题的核心价值不是让你背数据结构定义而是训练指针移动和边界判断这两点在嵌入式代码里同样是基本功。我自己刷链表题的一点体会是代码写错不可怕怕的是不看推导直接照抄模板。链表相交和环形链表II的解法都很短但如果没有把“两个指针同时走相同路程”和“a(n-1)(bc)c”这两个结论想明白面试时换个问法就会卡壳。所以建议你拿到这道题先别急着看题解在纸上画三个节点、一个环自己推一遍距离关系再回来写代码。那时候你会发现代码短到不需要背因为每一步都在逻辑里。打卡还在继续下一轮我准备整理哈希表和字符串双指针的题目到时候再把这些“边刷边沉淀”的笔记发出来。