企业官网建设流程全解析

刷链表题的时候，很多人都有一种错觉：指针指来指去，画个图就能搞定。但真到了写代码的环节，只要漏掉一个next的保存，或者循环条件多写一个等号，整个程序就直接说崩就崩。Day4 我集中把 LeetCode 上三道链表题打穿了：24. 两两交换链表中的节点、19. 删除链表的倒数第 N 个节点、142. 环形链表 II。这三道题表面上看各管各的，实际上把链表题最核心的考点全占了：指针重连、边界处理、快慢指针、数学推导。

这篇文章不打算按题号一个个念答案，而是把每一题的思考过程、为什么选这个写法、我实际跑代码时踩过的坑全部摊开讲。如果你正在准备算法面试，或者刷题速度一直卡在"看懂题解但自己写不出来"的状态，这三道题的拆解思路应该能帮你省掉不少时间。

1. 先聊清楚：链表题为什么总是"一看就会，一写就错"

链表这个结构本身非常简单，每个节点就存两个东西：一个值val，一个指向下一个节点的指针next。用 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) {} };

就这么点东西，看起来完全没有难度。但一到操作题，尤其是涉及删除、交换、反转的题，立刻就开始"指针丢了""空指针访问""死循环"轮番上阵。

根源在于很多人把"图解"当成了"理解"。看题解画一个箭头调整图，觉得每一步都对，但自己动手写的时候，面对的是一行行抽象的指针赋值语句，大脑里的箭头图跟代码根本对不上。链表操作的本质是通过内存地址（指针）重新组织节点之间的连接关系，每次修改一个next字段，等于把一条绳子剪断再重新接上，而这个动作是不可逆的。一旦先改了 A 的 next，B 的原始后继信息就丢了，后面想再访问就只能拿着悬空的指针去撞空地址。

所以刷链表题有一个总原则：先想清楚"会丢失哪条引用"，再动手写。而解决"引用丢失"的通用武器就是临时变量保存，以及哑结点（dummy node）统一边界。

再说一个常见误区：刷题喜欢追求"一遍遍历 + 原地操作"，这本身没错，但如果你对链表还不熟，先保证正确性，再谈优化。我见过不少人一上来就写空间复杂度 O(1) 的解法，结果连空链表、单节点链表都没测，交了两次才发现边界崩了。这三道题正好覆盖了链表题的经典边界场景，刷完你会对"空指针检查"特别敏感。

2. 两两交换链表中的节点：核心不是交换而是"重新接线"

题目要求不修改节点内部的值，只调整节点之间的指针关系，把相邻两个节点交换位置。比如1 -> 2 -> 3 -> 4，交换后变成2 -> 1 -> 4 -> 3。如果链表的节点个数是奇数，最后一个节点保持不动，比如1 -> 2 -> 3变成2 -> 1 -> 3。

2.1 先说递归写法：为什么它反而好懂

很多人排斥递归，总觉得递归是"玄学"。但这道题的递归写法非常符合人类的直观思维。

假设我现在需要交换head和它后面那个节点head->next。交换之后，新的链头是head->next，而head->next这个位置挂的应该是后面子链表交换完的结果。翻译成代码就是：

ListNode* swapPairs(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = head->next; head->next = swapPairs(newHead->next); newHead->next = head; return newHead; }

这个写法的妙处在于：你完全不用去管后面还剩多少节点，只需要相信"swapPairs(newHead->next) 会把后面的链表两两交换完并返回新的头节点"。递归的终止条件是链表中不足两个节点，直接返回。整个思考成本瞬间变小。

但递归解法有两个问题。一是如果链表很长，递归深度可能引发栈溢出，虽然面试中考这个点不多，但心里要有数；二是很多人递归写顺了，回头一看迭代版本反而不知道怎么打"从递归到迭代"的转换。所以接下来重点讲迭代。

2.2 迭代写法的三个关键步骤

迭代的核心思路是：用一个指针cur指着当前要交换节点对前面的那个节点，然后调整三根指针的关系。为什么要强调"前面那个节点"？因为如果你直接拿头节点去交换，交换完之后整个链表的头就变了，不处理的话返回结果时都不知道该返回谁。所以需要引入哑结点：

ListNode* swapPairs(ListNode* head) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* cur = dummy; while (cur->next != nullptr && cur->next->next != nullptr) { ListNode* first = cur->next; ListNode* second = cur->next->next; first->next = second->next; second->next = first; cur->next = second; cur = first; } return dummy->next; }

拆开来看，最核心的是cur的三个动作：

1. 先保存两个节点：first = cur->next和second = cur->next->next。为什么不直接在赋值语句里不停地写cur->next->next->next？因为长链式访问不仅可读性差，而且在修改cur->next之后再访问类似cur->next->next这种表达式，含义已经变了，很容易拿到错误节点或者空指针。

2. 调整内部连线：first->next = second->next。这一步是把第一个节点的后继指向第二个节点的后继。注意这时候second和它后面的链表还是"连着"的，所以second->next还能正确取到，不会丢链。

3. 更换头部顺序：second->next = first，再让cur->next = second。这一下second成了这对节点中的新头，而first被排到它后面。

4. 移动cur：cur = first。切记不要把cur挪到second上去。因为下一轮要处理的是first后面的两个节点，cur必须停留在"即将处理的节点对的前一个位置"，也就是当前这对节点的后半部分first。这个细节我当初写错过几次，直接把cur = cur->next->next一写，整个链表的指针就乱了。

2.3 实测中最容易翻车的三个场景

• 链表中只有两个节点：head = 1 -> 2 -> nullptr。第一次循环cur->next != nullptr和cur->next->next != nullptr都满足，交换完之后cur->next变成2，cur挪到1。下一轮cur->next是空指针，循环结束。整个过程没问题，但你必须在写 while 条件时先判断cur->next再判断cur->next->next，顺序反过来就是空指针访问。
• 链表只有三个节点：比如1 -> 2 -> 3。第一轮交换1和2变2 -> 1 -> 3，然后cur停在1，第二轮的cur->next是3，但cur->next->next是空，所以不会进入循环，末尾节点保持原样。这正好符合题目的奇数个节点要求。
• 忘记dummy->next才是最终返回的头：交换完成后真正的链表头是dummy->next，不是head。因为原head可能在第一轮就变成了第二个节点。很多人测试时链表长度大于 2，一 returnhead就会发现开头少了一个节点。

从这道题能总结出的一个通法：凡是"链头可能发生变化"的操作，都可以在前面放一个哑结点，让dummy->next永远是最终需要返回的头节点。这道题如此，下一道删除倒数第 N 个节点也是如此。

3. 删除倒数第 N 个节点：哑结点配合快慢指针的组合拳

题目要求删除链表的倒数第 N 个节点。1 -> 2 -> 3 -> 4 -> 5，N = 2，删除后变成1 -> 2 -> 3 -> 5。最笨的办法是两遍遍历：第一遍算出链表长度len，第二遍走到len - N的位置，跳过下一个节点。这是 O(L) 时间、O(1) 空间，其实已经合格了。但题目有个附加意义：用一次遍历完成删除，这就要请出快慢指针。

3.1 为什么快慢指针能做到一次遍历

设两个指针fast和slow，初始都指向哑结点。先让fast往前走 N 步，然后两个指针同步往前走。当fast到达链尾空指针时，slow恰好停在目标节点的前一个节点。这样一来，删除操作就变成了标准的"跳过下一个节点"：

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* fast = dummy; ListNode* slow = dummy; while (n > 0) { fast = fast->next; n--; } while (fast->next != nullptr) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return dummy->next; }

第一次写的时候，最容易纠结的问题是：为什么while (n > 0)让fast走 N 步，而不是 N-1 步？因为我们要让slow停在目标节点的前驱上。如果fast先走 N-1 步，同步移动到fast到链尾时slow正好指向目标节点本身，那删除slow指向的这个节点就很别扭。走 N 步之后，同步移动停止的条件是fast->next == nullptr，此时slow和目标节点之间正好隔着一个节点，直接slow->next = slow->next->next就能干净地摘掉目标节点。

3.2 边界条件一：删除的就是头节点

假设链表是1 -> 2，N = 2，要删除倒数第二个节点，也就是正数第一个节点1。如果用普通做法，不管 head 是直接给你变掉了，返回还是原来的 head 就会出错。但有了dummy之后一切照常：

• fast从dummy出发走 2 步，停在节点2上。
• 然后fast和slow同步移动。fast->next为空，触发停止，slow还停在dummy上。
• 此时slow->next是原来的头节点 1，执行slow->next = slow->next->next，就把 1 删掉了。
• 最后返回dummy->next，就是删完之后的节点 2。

整个过程中，头节点是不是被删，根本不需要单独判断。这就是哑结点统一边界的价值：删头节点和删中间节点用同一套代码。

3.3 边界条件二：链表只有一个节点

链表1，N = 1。fast从dummy走 1 步到节点 1，然后 while 判断fast->next为空，直接跳过。此时slow在dummy上，slow->next = slow->next->next，这条赋值语句的右边是nullptr，所以dummy->next变成空，返回空链表。逻辑完全正确。

3.4 我踩过的一个隐藏坑：内存释放

这道题在工程层面还有一个点：删除节点之后，如果是在真实项目中，你应当把被删除节点的next置空并释放内存，否则可能造成内存泄漏。很多刷题环境不在意这一点，但面试官偶尔会追问。所以可以补一手：

ListNode* tmp = slow->next; slow->next = slow->next->next; delete tmp;

注意：如果直接用delete slow->next，会先删除节点再给slow->next赋值，结果就是访问了已释放的内存，直接崩溃。正确做法是先把要删除的节点存到临时变量，改完链接关系之后再释放。

3.5 快慢指针的另一种写法：先计数再走

有同学反馈，说"先遍历求长度，然后让一个指针走 len - N 步"这做法不好吗？也很好，而且不容易出错。快慢指针的好处是不需要先知道链表长度就能一次遍历完成。但如果对快慢指针理解不透，我更建议面试时先写两遍遍历，再主动提一句"我可以优化成一次遍历"。能给出两种方案，比憋着一种方案更强。

我在单独练这道题的时候，还测过 N 大于链表长度的情况。题目保证 N 合法，所以不需要额外处理，但为了严谨可以加一个防御：如果fast在走 N 步的过程中提前变成nullptr，说明 N 超出链表长度，直接返回head或者报错。这在实际工程接口里是个不错的习惯。

4. 环形链表 II：从双指针到数学证明的完整链路

142 题在 LeetCode 上的难度标注是中等级别，但我个人感觉它的"思维难度"比 24 和 19 都高。因为前面两道题靠画图就能搞定，这道题就算画了图，如果不理解背后的数学原理，代码很容易变成"背下来的套路"。

题目要求：判断链表是否存在环，如果存在，返回环的起始节点。

4.1 哈希表的思路为什么不够优雅

最直观的做法是遍历链表，每到一个节点就把它的地址存进哈希表。如果某个节点的地址已经在哈希表里，说明环出现了，而且这个节点就是环的入口。

ListNode *detectCycle(ListNode *head) { unordered_set<ListNode*> visited; while (head != nullptr) { if (visited.count(head)) { return head; } visited.insert(head); head = head->next; } return nullptr; }

这个解法是正确的，空间复杂度 O(n) 也是题目能接受的，但面试官大概率会问一句："能不能把空间复杂度降到 O(1)？" 这时候就要上快慢指针。

4.2 快慢指针相遇的直觉理解

设置两个指针，slow每次走一步，fast每次走两步。如果链表无环，fast会比slow先到终点，流程自然结束。如果链表有环，fast进入环之后会在环里一直绕圈，slow进入环之后也被困在环里。因为fast每次比slow多走一步，相当于它俩在环上的距离每一轮缩减 1，所以必然在有限步内相遇。整个过程不需要额外空间，只需要在相遇点停下。

这也是为什么快慢指针检测环的有效性，跟环的长短、入口位置都无关。哪怕环长得离谱，只要步差恒定是 1，追上就是迟早的事。

4.3 相遇之后怎么找入口：完整数学推导

这是整个 142 题最核心的地方：相遇点不一定是环的入口。那为什么下一步只要"一个指针从头节点出发，另一个从相遇点出发，每次各走一步，再次相遇的位置就是环入口"？

设从链表头到环入口的距离为 a，从环入口到快慢指针相遇点的距离为 b，环的周长为 c。

• 慢指针走的距离是a + b。
• 快指针走的距离是a + b + k*c，其中 k 是快指针在环里多绕的圈数。
• 因为快指针速度是慢指针的两倍，同一时间内快指针走的距离 = 2 × 慢指针走的距离，所以：

a + b + k*c = 2 * (a + b)

化简得：

a + b = k*c

也就是说，a = k*c - b。换个写法：a = (k-1)*c + (c - b)。

这里的(c - b)是从相遇点继续往前走，直到回到环入口的距离。所以一个指针从链表头出发走 a 步到达环入口时，另一个从相遇点出发，先绕完整数圈(k-1)*c，再走(c-b)，也会到达同一个环入口。

结论就是：相遇之后，一个指针从头走，一个指针从相遇点走，速度一致，它们一定在环入口处碰头。

注意这个推导里并没有要求k = 1，快指针可能绕了很多圈才追上，但多绕的圈数在等式里刚好被消化掉，不影响最终结论。这也是这个解法让人放心的地方。

4.4 代码实现与空指针检查

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* ptr1 = head; ListNode* ptr2 = slow; while (ptr1 != ptr2) { ptr1 = ptr1->next; ptr2 = ptr2->next; } return ptr1; } } return nullptr; }

代码不长，但有三个必须注意的细节：

• while 的循环条件必须先检查fast再检查fast->next。因为循环体内有fast = fast->next->next，如果fast->next是空指针，那fast->next->next就是空指针访问。顺序不能反过来写。
• 为什么slow初始指向head而不是哑结点。这道题不修改链表，所以不需要哑结点，直接用头节点最自然。快慢指针初始指向同一个位置，不会有问题。
• 相遇后找入口的循环里不需要判空：因为已经确定存在环，ptr1和ptr2一定会在入口相遇；如果代码逻辑没写错，这个循环不会死循环。但为了防御，你可以在 while 条件里也加上ptr1 != nullptr && ptr2 != nullptr，工程代码里这么写更稳。

4.5 一个容易误解的点：为什么相遇位置不确定也没关系

我看过一些题解，试图提前算出快指针会绕几圈，算完把自己绕晕了。实际上你根本不需要知道 k 的具体值，正因为a = (k-1)*c + (c-b)对任意正整数 k 都成立，所以"从头走一个指针 + 从相遇点走一个指针"这个方案才永远有效。这个结论可以用一个最小样例验证：

链表1 -> 2 -> 3 -> 4 -> 2。头到入口的距离 a = 1（节点 1），环的入口是节点 2，环的周长 c = 3（2 -> 3 -> 4 -> 2）。慢指针进环走 1 步到节点 3 时，快指针很可能已经绕了一圈多，但这个"绕了几圈"完全不影响最终相遇点落在入口 2 上。真跑到代码里，你也会发现结果符合推导。

5. 连刷三题之后，我总结出的链表题通用规律

三道题刷完，最直接的感受是：链表题虽然变化多，但高频考点的重复性非常高。把这些规律单独写下来，是我这次刷题最大的额外收获。

5.1 只要链头可能变，就先套一个哑结点

24 和 19 题都用到了哑结点，因为这两题都可能让原链表的头节点被换掉或被删掉。哑结点本质上是一个"虚拟的前驱"，让所有操作都在一个统一的模式下进行，省掉了大量 if 判断。当你写代码发现"如果删除的是头节点，会不会有问题"时，大概率就该考虑加哑结点了。

5.2 空指针判断的顺序永远是一个模板

凡是涉及p->next->next这种连续两层访问，循环条件里必须先确认p != nullptr，再确认p->next != nullptr。这个顺序不能反过来，否则即使逻辑上觉得"链表足够长"，运行时也可能在某个边界样例上直接崩溃。这个模板我建议直接背下来：

while (p != nullptr && p->next != nullptr) { // ... }

5.3 快慢指针是链表题的"万能变体"

这几天刷题刷下来，快慢指针这个套路至少能解决四类问题：

• 检测链表是否有环：快指针每次走两步。
• 找环形链表的入口：相遇后从头再走一个指针。
• 找链表的中点：快指针到末尾，慢指针正好在中点。
• 找倒数第 N 个节点：快指针先走 N 步，再同步移动。

这四种场景的代码框架几乎一模一样，只在初始化移动步数上有细微差别。如果面试抽到链表题，先想想"这题能不能用快慢指针解决"，命中率相当高。

5.4 写完代码之后，用最小用例做边界自测

我刷这三道题时的自测用例固定是这五个：

• 空链表：nullptr
• 单节点链表：1 -> nullptr
• 双节点链表：1 -> 2 -> nullptr
• 奇数长度链表：1 -> 2 -> 3 -> nullptr
• 环连接在头/中/尾的不同情况

每一个用例跑一遍，能覆盖 90% 的边界错误。尤其是双节点和单节点，很多看似正确的解法是在这两个用例上崩的。养成这个习惯之后，面试时你甚至可以主动提出"我先跑几个边界用例"，这比闷头写完就交更能体现工程素养。

最后补充一个小技巧：刷链表题时不要只在脑子里跑代码，在纸上画出每一步指针的变化，尤其是slow和fast的位置。我前几年觉得自己已经是"看图理解"了，后来发现画图不是目的，画图是为了让你在程序崩溃之前，先在纸上发现指针断链的问题。Day4 的三道题，难度上有明显的递进：24 练指针重连，19 练边界处理，142 练思维推导。刷完之后再回头看链表题，你会发现自己已经有了一个很清晰的"套路库"，不管是面试还是写业务代码里的链表逻辑，都不慌了。