企业官网建设流程全解析

打卡刷题到第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 == nodeB，C++里指针相等表示它们指向同一个内存地址，这才是链表题目里“相交”“成环”的真正含义。

还有一个容易忽略的细节：链表题经常需要对头节点做特殊处理，比如链表只有一个节点时head->next为空，在做快慢指针时如果不提前判断就会越界访问。养成一个习惯：拿到链表题先想清楚“空链表”“单节点”“双节点”三种边界情况，再开始写代码。

2. 链表相交：双指针“路程拉平”的推导与代码

2.1 题意拆解与两种主流思路

链表相交的题面是这样的：给定两个单链表的头节点headA和headB，如果两个链表相交，返回相交的起始节点；如果不相交，返回nullptr。题目默认这两个链表都没有环。

先想一个特别朴素的解法：遍历链表A的每一个节点，对于每个节点，再去遍历链表B看有没有相同地址的节点。这种做法的时间复杂度是O(m*n)，一旦链表长度上千，跑得很慢，面试官基本不会接受。

稍微优化一点的做法是把A的所有节点指针存进哈希集合，然后遍历B，第一个在集合里出现的节点指针就是交点。时间O(m+n)，空间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_set<ListNode*> 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 + b，fast走过的总路程是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 vector<int>& 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 常见问题与排查速查表

链表题的报错往往非常直接，不是“段错误”就是“超时”，但如果不知道原因，排查起来很费劲。我把这两道题最常见的坑整理成一张速查表，每一行都是实际踩过或见别人踩过的：

最值得反复强调的还是判空顺序：在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的推导花了快一个小时，画了三四张图，但画通之后，代码就再也忘不掉了。如果你也卡在链表题，别急着背代码，先拿张纸把指针的移动轨迹画出来，这一步做扎实了，后面会顺利很多。