企业官网建设流程全解析

刷题打卡进行到第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(n+m)，空间O(n)。这个解法能过，但面试里更希望看到空间O(1)的双指针法。双指针的思路非常对称：pA从headA出发，pB从headB出发，每次各走一步；pA走完链表A之后，跳到headB继续走，pB走完链表B之后，跳到headA继续走。两个指针最终要么在相交节点相遇，要么同时走到nullptr返回空。

为什么这个做法成立？假设交点前链表A的长度是a，链表B的长度是b，交点后公共部分长度是l。pA完整走过的路径是a + l + b，pB完整走过的路径是b + l + a，二者的路径长度完全相等，所以当它们各自走完自己的路径时，会同时停在交点处。如果两条链表根本没有交点，那pA走完A+B的长度后落在nullptr，pB走完B+A的长度后也落在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_set<ListNode*> 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放在head，index2放在相遇点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。
• 整个链表就是一个环，入环点在head：a = 0，index1从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 可执行文件名

或者更常见的写法用g++：

g++ -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可以直接跳到定义，Shift+F12可以查看所有引用；或者按住Ctrl键，再用鼠标点击函数名，也能跳转。链表题里最常见的用法是单击ListNode结构体定义跳转到头文件，确认成员变量名字；在长文件里想回到刷题主函数，按一下Ctrl+-就能回到上一个位置。

如果按F12没反应，多半是IntelliSense没有索引当前文件。可以按Ctrl+Shift+P，输入“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时见过的：

这张表里的第一条是我自己印象最深的，因为它在链表题里是最隐蔽的。很多报错信息不会告诉你是哪一行，只告诉你空指针访问，这时候在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)(b+c)+c”这两个结论想明白，面试时换个问法就会卡壳。所以建议你拿到这道题先别急着看题解，在纸上画三个节点、一个环，自己推一遍距离关系，再回来写代码。那时候你会发现，代码短到不需要背，因为每一步都在逻辑里。打卡还在继续，下一轮我准备整理哈希表和字符串双指针的题目，到时候再把这些“边刷边沉淀”的笔记发出来。