企业官网建设流程全解析

代码随想录算法训练营Day04，链表part02。能走到这一天的同学，大概率已经在前一天被707设计链表的手写节点搞得有点懵了，结果第二天一来就是四道硬题。这四道题分别是：24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题02.07. 链表相交、142. 环形链表II。我刚刷完时觉得它们不难，真正复盘时才发现每一道都在考验同一个底层能力：改指针前，必须清楚还有没有别的指针指着当前节点。这篇记录我打算把每一题的思考过程、代码、推导、边界条件都摊开讲，适合正在跟营打卡的同学，也适合任何刚开始啃链表题的人。

1. 为什么链表part02的四道题值得单独拎一天

1.1 这不是四道孤立的题，是一套完整的能力矩阵

很多人第一天拿到Day04的打卡清单，第一反应是“就四道题，还好”。但这四道题放在一起，恰好覆盖了链表题型里最常用的四种核心手法。

part01的三道题（203移除链表元素、707设计链表、206反转链表）只解决了一个问题：会遍历、会增删、会改指针方向。而part02这四道题，每道都多走了一步。24题要求你同时保住两个甚至三个节点不被覆盖，19题要求你理解双指针之间的间距，02.07要求你理解链表尾部的结构一致性，142题直接进入证明题模式。把它们拆开看是四种解法，合起来看是一套完整的链表能力矩阵。

1.2 训练营选题顺序背后的梯度

训练营的排题顺序不是随便定的。203移除链表元素，第一次引入虚拟头节点这个概念，让你知道“头节点没有前驱时该怎么统一处理”。707设计链表更狠，要求你手写get、insert、delete，相当于把单链表的增删改查全过了一遍。206反转链表则是多指针操作的第一次正面接触，prev、cur、next三个指针同时维护，一不小心就丢节点。

到了part02，两两交换直接就是反转链表的plus版。反转链表只用维护三条指针关系，两两交换要维护的节点更多，还要在交换后正确跳到下一组。删除倒数第N个节点把快慢指针引进来，这是链表题里最高频的双指针套路之一。链表相交要求你从“两个链表形状不同”里找到它们的公共尾部，本质上是在练长度关系。环形链表II更是把快慢指针和数学推导放在一起，直接劝退了一批人。这个坡度爬下来，对新手是友好的，因为你每一步都站在前一天已经练过的能力上。

1.3 part02真正考的是“改指针之前想清楚后面”

我一直觉得，链表part01练的是“怎么移动指针”，part02练的才是“如何管理多个指针之间的关系”。这两者差别很大。移动指针只需要知道 next 往哪走，但管理多个指针，你得在脑子里维护一张状态图：当前这块内存到底被几个指针引用着？我改掉其中一个，会不会让另一个指针失去访问路径？

两两交换里，你要用一个临时指针保存第三节点，就是因为改了前两个节点的指向之后，第三个节点可能会从主链上“消失”。删除倒数第N个节点里，你要让快慢指针之间保持一个固定间距，本质上是在用两个指针描述“倒数第N个”这个位置。链表相交里，你要通过对齐让两个指针落在同一个起点，然后用地址一致来判断交集。环形链表里，你要让快慢指针在环内相遇，再用数学关系反推入口。四道题本质都在做同一件事：利用多个指针之间的相对位置关系，描述链表里的“第几个”“交叉点”“入口”。这个思想一旦打通，后面再做链表题，很多题你都会发现是同一个套路换了层皮。

2. 四道题逐题拆解：思路、代码、为什么

2.1 两两交换链表中的节点：先保住后路再动手

先看24题，题目要求把相邻的两个节点交换位置，不是改值，是改指针方向。最直观的迭代做法是，在链表头前面加一个dummy节点，然后每次处理一对节点时，把两个节点交换，再把当前指针跳到下一对节点的前驱位置。

为什么要dummy？因为真正的头节点没有前驱，如果直接处理head，交换后的新头节点会变成head.next，虽然也能返回对，但你在循环里需要一个“指向当前这对节点的前一个节点”的指针，head前面没有节点，就只能特判。dummy存在的意义，就是把这种特判从循环里干掉。让dummy指向head，然后从头开始统一处理，最后返回dummy->next，这样不管链表原本多长，逻辑都完全一致。

交换的代码最容易栽的地方是顺序。一旦你把cur->next指向node2，node1就失去了从cur出发的引用，所以必须先把node2->next和后面那一堆节点保存下来，或者至少保存nextPair。

class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummy = new ListNode(0, head); ListNode* cur = dummy; while (cur->next != nullptr && cur->next->next != nullptr) { ListNode* node1 = cur->next; ListNode* node2 = cur->next->next; ListNode* nextPair = node2->next; cur->next = node2; // 第一步：把前驱指向node2 node2->next = node1; // 第二步：让node2指向node1 node1->next = nextPair; // 第三步：让node1指向下一对的起点 cur = node1; // 下一轮要处理的是node1后面的两个节点 } ListNode* result = dummy->next; delete dummy; return result; } };

这段代码里最容易被忽略的是最后一行 cur = node1。交换完之后，node1被换到了node2的后面，而node1正是下一对待处理节点的前驱。如果你写成cur = cur->next->next，也可以，因为此时cur->next是node2，node2->next是node1，但直接写cur = node1更直观，也不容易算错。

写完拿两个节点的用例走一遍：dummy->1->2->null，交换后dummy->2->1->null，返回2。这个case过掉，基本就过了一半。再把三个节点的case过一遍，你会发现在循环终止条件的判断上，cur->next和cur->next->next这两个条件缺一不可。

2.2 删除链表的倒数第N个节点：一次遍历的关键是多走一步

删除倒数第N个节点，最朴素的做法是先遍历一遍求长度L，再遍历一遍删除第L-N+1个节点。这是两遍遍历，时间复杂度O(n)，在LeetCode上能过，但面试官通常会追问“能不能一遍？”能，用快慢指针。

具体做法是：定义fast和slow都指向dummy，先让fast走n+1步，然后fast和slow一起走。当fast走到null时，slow正好停在待删节点的前一个位置上。

为什么是n+1而不是n？因为要让slow停在待删节点前面。如果只走n步，fast到null时slow会停在待删节点上，要删除当前节点就得拿到前驱，这就被迫多保存一个prev指针，反而更麻烦。让fast多走一步，就是把slow和待删节点之间的距离拉开一格，slow自然就站在了前驱的位置上。

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0, head); ListNode* fast = dummy; ListNode* slow = dummy; for (int i = 0; i <= n; i++) { fast = fast->next; } while (fast != nullptr) { fast = fast->next; slow = slow->next; } ListNode* toDelete = slow->next; slow->next = slow->next->next; delete toDelete; return dummy->next; } };

一眼看过去，这个解法最大的疑问是：fast先走n+1步，后面while循环又同时走，慢指针怎么就知道自己停在正确位置了？你可以这样理解：fast走到null时，它一共走了L+1步（dummy到null的距离）。而fast永远比slow多走n+1步，所以slow就走了(L+1)-(n+1)=L-n步，也就是从dummy往后数L-n个节点，这个位置正好是倒数第n+1个节点，也就是待删节点的前一个。这个结论用一个小例子验证一下，链表1-2-3-4-5，删倒数第2个，也就是删4，fast先走3步到3，然后两指针同步到fast为null，slow落在3上，清理3->next=5，完成。

还有一个细节：fast先走n+1步这个操作，依赖题目保证n合法。LeetCode这题有约束，但如果你在工程里写，n可能大于链表长度，要在循环里判断fast是否为空。写防御性代码不是多余，而是好习惯。

2.3 链表相交：比的不是值，是地址

链表相交这题有个经典坑：把node.val相等误当成相交点。两个单独的节点即使值相同，也不是同一个节点，只有指针地址相同，才表示它们共享同一段链表。这个一定要记牢。

思路其实很简单：相交节点之后的长度必然相同。两个链表只有相交之前的部分可能不一样长，所以先各遍历一遍求长度，让较长的那个链表先走差值步，然后两个指针同步前进，第一个地址相同的节点就是答案。

class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA = 0, lenB = 0; ListNode* curA = headA; ListNode* curB = headB; while (curA) { lenA++; curA = curA->next; } while (curB) { lenB++; curB = curB->next; } curA = headA; curB = headB; if (lenA < lenB) { swap(lenA, lenB); swap(curA, curB); } int diff = lenA - lenB; while (diff--) curA = curA->next; while (curA != nullptr && curB != nullptr) { if (curA == curB) return curA; curA = curA->next; curB = curB->next; } return nullptr; } };

第二种更简洁的写法是双指针走A+B。pA先遍历A，走完之后去遍历B；pB先遍历B，走完之后去遍历A。两个指针走的总步数相同，如果有交点，它们会在交点相遇；如果没有交点，它们会同时走到null。这个方法不用算长度，我第一次看到觉得有点神奇，但自己想一遍就明白了：A+B和B+A是长度完全相同的两个拼接序列，从中点把两个目标链对齐之后，任何相同的后半段都会在同一个步数上出现。

比较指针地址这步，C++里直接写if (curA == curB)，Java里也是等号比较引用，Python里则建议用is或者用id(curA) == id(curB)，别用==，因为Python可能在类上重载了__eq__，比较结果会跑偏。

2.4 环形链表II：快慢指针也离不开数学

最后是142题环形链表II，这题才是当天的分水岭。判断有没有环很简单：快指针每次走两步，慢指针每次走一步，如果存在环，快指针一定会在环里追上慢指针。为什么一定能追上？因为步长差是1，慢指针进环之后，快指针每次都会把相对距离缩小1，不会跳过，所以不可能出现两个人交错而过但没撞上的情况。

但是题目要返回环的入口，这就得多算一步。设头节点到环入口的距离为a，环入口到第一次相遇点的距离为b，相遇点继续绕回环入口的距离为c，那么环长就是b+c。慢指针从head走到相遇点，总路程a+b；快指针走的路程是a+b+n(b+c)，因为它可能已经在环里绕着走了n圈。由于快指针速度是慢指针的2倍，所以：

2(a+b) = a+b+n(b+c)

移项化简得到：

a+b = n(b+c)

再拆一下：

a = n(b+c) - b = (n-1)(b+c) + c

这个式子的核心含义是：头到入口的距离a，等于从相遇点继续走c步回到入口的距离，再加上若干个整圈。整圈不影响位置，所以结论是：相遇之后，把一个指针放回head，另一个留在相遇点，两个指针都每次走一步，它们一定会在环入口相遇。

class Solution { public: ListNode *detectCycle(ListNode *head) { 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 = slow; while (index1 != index2) { index1 = index1->next; index2 = index2->next; } return index1; } } return nullptr; } };

代码很短，但只有亲手把上面的推导写一遍，你才能真正理解为什么相遇之后要一快一慢同步走。如果只是背代码，换个问法“求相遇位置”你就懵了。这个推导在评论区里被问过无数次，答主也反复强调，所以别偷懒。

3. 实操复盘：跟着我完整过一遍24题的实现过程

3.1 画图是第一生产力

写链表题，我的习惯永远是先画图。画法很简单：把每个节点画成一个方块，里面写val，右边画个箭头指向next，再用带圈的小标签标出当前有哪些指针。24题画四个节点，标上dummy、cur、node1、node2、nextPair，然后每执行一行代码，就擦掉原来的箭头，画上新箭头。这个动作看着慢，实际是最高效的debug方式。

我记得第一次画的时候，一开始总是漏掉nextPair这个箭头。为什么？因为我习惯性地以为node2->next就是node1，其实那是在交换之后才成立的。交换之前，node2->next指向的是第三节点，一旦你改了node2->next，第三节点就从主链上消失了。画图上你只要把nextPair箭头擦掉，立刻就意识到必须提前保存。代码里漏掉一行，编译器可能不报错，但画图能让你一眼看出来。

3.2 代码是画图的自然产物

把画图顺序翻译成代码，基本就是这么几步：先创建dummy并指向head，cur指向dummy；循环条件写成cur->next和cur->next->next都不为空；交换三个箭头；最后cur跳到node1的位置。每一行代码都能在纸上找到对应那根箭头。

没有这张图直接背代码，很容易在while条件里加错一个next。我当时是先写代码再画图验证，发现cur跳错了，改成cur=node1之后整个逻辑就通了。用文字描述就是：每次循环处理一对节点，处理完之后，当前这一对的第二个节点就是下一次处理的前驱，所以把cur放在node1的位置。

这里有一个非常容易踩的坑：如果你在循环里把node1->next改成了nextPair，但是忘记了提前存nextPair，那么第一次循环能过，第二次循环cur->next可能就变成了空，接下来访问cur->next->next直接空指针异常。这种错误刷题平台上报出来是“runtime error”，你得回头盯好几遍才找得到。

3.3 用边界用例自测一遍

链表题挂掉通常不是挂在复杂的中间流程，而是挂在边界。空链表、只有一个节点、只有两个节点、奇数个节点、偶数个节点、删除第一个节点、删除最后一个节点，这些case每个都值得手动跑一遍。我一般会在草稿纸上列一个边界用例表，就像下面这样：

这张表适用于part02四道题中的大部分，尤其24和19。建议刷完每道题，都把边界用例在编译器里实际跑一遍，不要只靠眼睛看。我在本地写了一个很小的测试函数，构造链表、调用目标函数、输出结果，整个过程不到一分钟，但能避免你明明逻辑很对却因为一个边界没处理被测试用例卡住。

4. 链表题高频翻车点排查

4.1 新手最容易踩的五个坑

链表题的报错大多长得一样，但原因各不相同。把这一阶段踩过的坑汇总成一张表，基本能覆盖80%的情况：

这五条里，第一条和第三条是出现频率最高的。第三条我第一天就犯过：new了一个dummy，返回时直接return dummy，结果多了一个0节点。这种错误别看小，浪费的时间一点不少，而且你在LeetCode上看到的报错往往是一个节点多出来，没有提示框，只能全靠肉眼扫。

4.2 五个万能的调试习惯

从上到下，总结几个我亲测有用的习惯：

1. 先纸上画状态图，不画不写代码。
2. 每次改指针之前问自己：当前节点还有没有别的指针引用它？如果只有一根指针指向它，先拿临时变量保存再改。
3. 每个循环结束，确保至少有一个指针向前移动，否则八成是死循环。
4. 写完跑边界用例，空、单节点、双节点、首尾删除都过一遍。
5. 一个函数只干一件事，链表题的辅助函数越少越好，否则传指针容易传错。

这五条基本是从错误里长出来的。比如第3条，很多人写循环条件时用while(cur->next)，但循环体里却把cur->next改成了别的，导致cur永远没往前走，链表直接成环。这种情况代码看起来完全合法，编译器不会报错，只能靠调试习惯兜底。

4.3 不同语言下链表实现的差异

刷题平台最常见的是C++、Java、Python。C++里节点用结构体定义，指针类型是ListNode*，空指针是nullptr；Java里节点是class，引用类型，默认null；Python里节点也是class，每个对象都有id，判断相交用is或者id(a)==id(b)，不要用==，因为Python的==可能触发值比较。这里给一个C++结构体链表基本语法的参考：

struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} };

看到这段代码不用背，但要知道构造函数有三种写法，分别对应不传值、只传val、传val+next。707设计链表里手写这些构造函数是基础，到part02写题时都默认会用。如果你用的是Python，节点定义通常是：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

Python刷链表有个特性：变量赋值本质上是引用，所以你把一个节点赋给另一个变量，它们指向同一个对象，用is判断就能确认身份。这一点在链表相交题里特别重要，因为如果你用==，在自定义类没重载__eq__时可能没问题，但一旦加了值比较逻辑，结果就完全错了。

5. 跳出训练营：链表part02能延伸到哪些地方

5.1 训练营之外值得补的几道题

刷完part02，链表部分的思维算是正式打开了。如果你还有余力，建议顺带把这几道题也补上：21.合并两个有序链表，这是dummy节点和指针移动的经典组合；25.K个一组翻转链表，这是反转链表的高配版，能把part02的“保后路”功夫练到极致。数据结构课和C语言课常布置的单链表基本操作实验、循环单链表、合并两个有序的单链表、基于链表的两个集合的差集，本质上也都是对part02能力的具体化。

比如合并两个有序链表，核心是维护一个cur指针，每次都指向两个链表头部较小的那个节点，然后被选中的链表往前进一步。你会发现这和24题里维护dummy和cur的思路是一模一样的：只要保证当前指针永远站在“待操作区域”的前一个节点，后面怎么接都不会乱。再比如基于链表做集合差集，其实就是两个有序链表同时遍历，值小的先走，值相等就跳过，这套逻辑和归并排序里合并两个有序序列的框架也是同源。

5.2 从刷题到工程：链表为什么还没有死

可能有人会问，刷链表题和真实工程有什么关系？关系很大。LRU缓存就是哈希表加双向链表；Redis的list类型底层也有链表；浏览器前进后退、文本编辑器撤销重做，都是栈或双向链表的经典应用；内存分配器里的free list，本质就是单链表；哈希表解决冲突用的拉链法，用的也是链表。

你在part02练的“快慢指针”，在找链表中间节点、找倒数第k个节点、判断链表是否有环这些场景里都是通用套路。链表这个数据结构不会因为数组看起来很香就退出历史舞台，它只是以更隐蔽的形式活在各种底层实现里。所以训练营把链表放在第四天，是很有道理的：它看起来只是数据结构入门，实际上是在为后面哈希表、栈、队列、图论里的邻接表积累手感。链表用不好，后面很多结构你都只能靠背。

5.3 关于复盘的几句话

最后想聊一下复盘。训练营第四天的题，我当时刷完是能AC的，但一周后再让我写一遍，24题漏了临时指针，142题的证明也讲不清。后来我调整了策略：不追求当天刷很多题，而是挑两三道核心题，第二天不看题解重新写一遍，写的时候顺手把推导过程写进注释。这个习惯坚持到链表part02结束，效果比刷十道新题好得多。

如果你正卡在Day04，别急着往后赶。把142题那个推导抄三遍，再关上题解手写一遍代码，你收获的东西会比空洞的打卡多得多。链表part02刷透之后，Day05开始进入哈希表，你会发现链表那份手感直接迁移过来了，很多题目写起来特别顺。祝刷题顺利。