企业官网建设流程全解析

如果你也在跟《代码随想录》这条刷题路线，我猜你前三天的心情大概是这样的：链表结构看懂了，增删改查能写了，反转链表也能磕磕绊绊跑通，于是觉得自己已经拿下了链表。直到 Day04，链表 part2 这四道题摆在面前，才第一次真正体会到“看懂了”和“做对了”完全是两码事。

这一天的题目分别是：两两交换链表中的节点、删除链表的倒数第 N 个节点、链表相交、环形链表 II。它们不涉及任何新的数据结构，全部基于单链表的基础操作，却把虚拟头节点、临时指针、快慢指针、数学证明这几个“成人礼”级别的技能一口气塞给了你。这篇就把我刷这四道题的全过程写下来，包括推导思路、代码、我踩过的坑，以及做完之后对链表操作的一些新理解。如果你正好卡在 Day04，希望这篇能帮你少走一点弯路。

1. day04 这四道题，到底想让你的链表基本功“会”到什么程度

1.1 从“会做题”到“能解释解法”的分水岭

前两天其实还在解决“链表是什么、怎么遍历、怎么插入删除”这类语法级问题。到了 Day04，题目难度并没有突然变成竞赛级，但它考察的东西变了：从“你会不会写链表操作”变成了“你能不能设计出一段不会把链表改坏的操作序列”。

我用一件事说明这个区别。删除一个普通节点，大多数人的第一反应是：找到前驱 prev，让 prev.next 跳过目标节点。这只是一条路径。但 Day04 里的题目，比如两两交换相邻节点，一次操作要动三到四条 next 指针，而且它们之间存在依赖关系：先改哪一条、后改哪一条，会直接决定链表会不会断掉。这已经不是“背语法”能解决的问题了，必须真的理解“指针是引用”这件事。

四道题放在一起看，其实覆盖了三条主线：

• 虚拟头节点怎么用才能消除头节点的特殊性；
• 双指针技巧在链表中最常见的两种形态：快慢指针、长度差对齐；
• 把链表问题“几何化”的能力：环形链表和相交链表，本质上是把链表路径画出来之后找数学关系。

这三条主线，恰好是后面二叉树、图论题目里反复出现的思维工具。所以 Day04 不是单纯的四道题，它是在帮你完成一次认知升级。

1.2 进入 day04 之前，我建议你先确认这几项基础

如果你带着知识漏洞直接冲这四道题，很可能每道题都会卡住，但又说不清卡在哪。我建议先把下面这几项基础过一遍，每个都能答上来再开始。

如果你发现上面表格里有模棱两可的地方，建议先回去把链表 part1 的设计链表、反转链表重写一遍，再回来做 Day04。我自己就是先补了反转链表里“三个指针怎么配合”的细节，再来做两两交换时，才觉得“原来是一回事”。

2. 两两交换节点：第一次真正意义上“玩指针”

2.1 为什么说它是“虚拟头节点”的最佳教学题

先看题目要求：给定一个链表，两两交换其中的相邻节点，并返回交换后链表的头节点。注意，不能只是改变节点的值，必须实际修改节点的 next 指向。这意味着输入 1 -> 2 -> 3 -> 4，要得到 2 -> 1 -> 4 -> 3。

为什么这道题是虚拟头节点的最佳教学题？因为交换头两个节点时，新的头节点变成了原来的第二个节点。如果你不用虚拟头节点，就得单独处理“当前要交换的这对节点的前驱是空指针”的情况，写出来的代码会长出一截，而且容易漏。

用虚拟头节点就变成了一个统一模型：我要交换 cur.next 和 cur.next.next 这两个节点，cur 始终指向被交换两个节点的前驱。第一轮 cur 指向 dummy，第二轮 cur 指向交换后的第二个节点，第三轮继续向后。这样一来，头节点的特殊性彻底消失，代码结构非常干净。

2.2 三个指针的移动顺序，就是这场交换的“搬运真谛”

直接上代码，我用 Python 写，C++ 思路完全一样，只是最后记得释放内存。

def swapPairs(head): dummy = ListNode(next=head) cur = dummy while cur.next and cur.next.next: # 保存本轮要操作的三个关键位置 first = cur.next # 第 1 个节点 second = cur.next.next # 第 2 个节点 third = cur.next.next.next # 下一轮的第一个节点 # 开始改指针 cur.next = second # 前驱指向第 2 个节点 second.next = first # 第 2 个节点指向第 1 个节点 first.next = third # 第 1 个节点指向后续链表的头 # cur 移动到交换后这对节点的“第二个位置”（即原来的 first） cur = first return dummy.next

我第一次写这段代码时，最困惑的是：为什么要提前保存 first、second、third 三个变量？直接改不行吗？

关键在于，一旦 cur.next 被改成 second，原来的 first 节点就只能通过cur.next.next找到，但如果你紧接着就把second.next改了，first 的引用依然还在，因为 first 变量保存了它。最危险的是 third：当cur.next = second执行后，如果你没有提前保存 third，再想取cur.next.next.next已经晚了——因为 cur.next 已经变成了 second，而 second.next 当时还没改，它指向的确实是原来的第一个节点，不是原来的第三个节点。这就会导致后面的链整个丢失。

所以一句话总结：改任何指针之前，先把那些之后还要访问的节点用变量存起来。这个意识，比这道题本身重要得多。

2.3 写代码时最容易翻车的三个细节

我把自己踩过的坑列在这里，基本覆盖了新手所有报错点。

第一个坑：循环条件写反。while cur.next and cur.next.next这个顺序不能换。如果链表只有一个节点，cur.next不为空，但cur.next.next是空，条件正常结束。可如果你先写cur.next.next，在空链表或者单节点链表上会直接访问 None.next，当场崩溃。这属于 Python 和 C++ 都会犯的低级错误，一定要把cur.next放在前面。

第二个坑：cur 移动位置搞错。交换完成后，cur 应该指向“交换后这一对的第二个节点”，也就是原来的 first 节点。因为下一轮要交换的是它后面的两个节点。如果写成cur = cur.next.next，交换 1、2 之后，cur 会指向 4，直接把节点 3 漏过去。

第三个坑：返回值写成 head。两两交换之后，原来的 head 已经变成了第二个节点，必须返回dummy.next。如果你返回 head，在某些用例下等于返回了错误位置的节点。这个问题在提交判题时非常容易暴露，因为前几个用例可能碰巧一样，后面的用例才出错。

3. 删除倒数第 N 个节点：一次遍历背后的两个“为什么”

3.1 快指针为什么先走 n+1 步，而不是 n 步

这道题的要求是删除链表的倒数第 N 个节点，进阶要求是一次遍历完成。最常见的错误思路是：快指针先走 n 步，然后快慢一起走，快指针到末尾时，慢指针正好指向倒数第 N 个节点。这个思路没问题，问题在于——指向待删节点本身，对删除操作没有任何帮助。

单链表的删除操作，核心是修改前驱节点的 next。如果你停留在待删节点上，你根本不知道它的前驱是谁。所以必须让慢指针停在待删节点的前驱位置。

怎么做到？让快指针先走 n+1 步。这样快指针比慢指针多走 n+1 步，当快指针走到空指针时，慢指针正好在倒数第 n+1 个位置上，也就是待删节点的前驱。

具体来说，用虚拟头节点 dummy，fast 和 slow 都从 dummy 出发。fast 先走 n+1 步，然后 fast 和 slow 同步一步一步走。当 fast 变成 None 时，slow.next 就是要删的节点，执行slow.next = slow.next.next即可。

3.2 一次遍历比两次遍历强在哪？

两次遍历的方案很直观：先算出链表长度 length，然后从头走到第 length - n 个节点，这个节点正是待删节点的前驱。时间复杂度同样是 O(n)，空间复杂度也一样。那为什么还要学一次遍历？

原因有两点。第一，一次遍历的“快慢指针错位”思想可以迁移到很多场景，比如找链表的中点（快走两步、慢走一步）、判断环形链表。你提前掌握这种错位结构，后面会省很多事。第二，在某些链表是“流式数据”、只能读一遍的场景下，两次遍历的方案根本不成立，一次遍历是唯一解。

另外，虚拟头节点在这里再次立功。如果删除的恰好是头节点，也就是 n 等于链表长度时，两次遍历方案里要单独写一个 if 判断。而用虚拟头节点，操作路径被统一了：fast 先走 n+1 步后变成 None，慢指针停在 dummy，slow.next = slow.next.next正好把头节点删掉。

3.3 用边界测试验证自己的实现

写完代码之后，我强烈建议你手动跑三个边界用例。很多看起来正确的代码，就是在这三个用例上暴露出问题的。

def removeNthFromEnd(head, n): dummy = ListNode(next=head) fast = slow = dummy # fast 先走 n+1 步 for _ in range(n + 1): fast = fast.next # fast 和 slow 同步走 while fast: fast = fast.next slow = slow.next # slow 指向待删节点的前驱 slow.next = slow.next.next return dummy.next

三个用例分别是：

• 链表只有一个节点，n=1。fast 走 2 步后变成 None，循环不执行，slow 还在 dummy，slow.next = slow.next.next把唯一节点删掉，返回 None。正确。
• 链表长度等于 n，删除头节点。比如 1 -> 2 -> 3，n=3。fast 走 4 步后变成 None，slow 停在 dummy，删除的是 head。正确。
• n=1，删除尾节点。fast 先走 2 步，然后 fast 和 slow 同步走，fast 到 None 时 slow 正好在倒数第二个节点，删掉最后一个。正确。

这三个用例跑通，基本说明你的实现没有边界问题。这个“边界测试”习惯，在后面刷二叉树时也会非常有用。

4. 链表相交：两个看似无关的思路，其实讲的是同一件事

4.1 先纠正一个直觉：比的是“节点本身”还是“节点的值”？

链表相交这道题，题目定义很关键：两个链表从某个节点开始，共用同一批节点。这里说的是“同一个节点对象”，而不是“两个值相等的节点”。

我见过很多人用值相等的判断来写这道题，结果在测试用例上翻车。因为两个链表完全可以出现值相同的节点，但它们并不是同一个节点。比如两个长度都是 3 的链表，都包含值为 2 的节点，但这两个节点在内存里是不同的对象，只是值碰巧相同。

在 Python 里，判断两个节点是否相同要用is，而不是==。C++ 里就是指针值是否相等。这个点看起来很小，却是整道题的地基。地基一旦错了，后续思路再漂亮都是错的。

4.2 末尾对齐法是怎么想到的

先看一个关键规律：如果两个链表相交，相交节点之后的所有节点都是同一个链表的延续，所以两个链表的“尾巴”是完全重合的。既然尾巴重合，交点之后的部分对两个链表来说长度一定相同。那么两个链表长度不一样，差的只可能是交点之前的长度。

基于这个规律，处理手段就很直接了：先分别算出两个链表的长度，然后让较长的链表先把长度差走掉，让两个指针站在同一起跑线上。之后两个指针同步前进，第一次遇到pa is pb的位置就是交点。如果走到 None 都没遇到，说明两个链表不相交，返回 None。

def getIntersectionNode(headA, headB): lenA = lenB = 0 pa, pb = headA, headB while pa: lenA += 1 pa = pa.next while pb: lenB += 1 pb = pb.next pa, pb = headA, headB diff = abs(lenA - lenB) if lenA > lenB: for _ in range(diff): pa = pa.next else: for _ in range(diff): pb = pb.next while pa and pb: if pa is pb: return pa pa = pa.next pb = pb.next return None

这个解法的时间复杂度是 O(m+n)，空间复杂度 O(1)，是面试里最稳妥的方案。理解它不需要额外的数据结构，只需要一张纸一支笔，把两条链画成“一个 Y 字型”，然后思考末尾对齐的过程。

4.3 双赛道接力法和哈希集合法的取舍

除了末尾对齐法，还有两种常见解法，我觉得都值得了解，因为它们对应着不同的取舍。

第一种是哈希集合法。遍历链表 A，把所有节点放进一个 set，然后遍历链表 B，逐个判断当前节点是否已经出现在 set 里。第一个命中的节点就是交点。这个写起来最简单，但空间复杂度变成 O(m)。在追求极致空间的场景下不如末尾对齐法，但胜在思路直白。

第二种是“双赛道接力法”。核心想法是让两个指针分别走完“自己的链 + 对方的链”，总路程一样。pa 从 headA 出发，走到末尾后跳到 headB 继续走；pb 从 headB 出发，走到末尾后跳到 headA 继续走。如果两链相交，两个指针会在交点相遇；如果不相交，它们会同时走到 None，循环结束。

def getIntersectionNode(headA, headB): pa, pb = headA, headB while pa is not pb: pa = pa.next if pa else headB pb = pb.next if pb else headA return pa

这段代码短小精悍，但前提是你要理解“总路程相同”这件事。为什么它们一定同时到达交点？因为 pa 走的总长度是 lenA + lenB，pb 走的总长度也是 lenA + lenB，而交点之后的路径对两者来说是一样的，所以在交点之前的部分必须通过“交换赛道”来对齐。不相交时，它们会在最后同时变成 None。三种方法本质是同一件事：想办法让两个链表的遍历在时间上对齐。选择哪种，取决于你是在刷题阶段追求熟练，还是在面试现场追求最短代码。

5. 环形链表 II：快慢指针相遇之后的那个“a = c”，怎么推导才不晕

5.1 先用一句大白话理解整个算法流程

环形链表 II 要求判断链表是否有环，如果有，返回环的入口节点。很多同学的困惑来自它有两步操作，而且第二步为什么要那么做，完全不直观。我先把流程说清楚：

1. 快指针每次走两步，慢指针每次走一步，从 head 同时出发。
2. 如果快指针走到了 None，说明链表无环，返回 None。
3. 如果快慢指针相遇了，说明有环。此时把快指针重新放回 head，然后让快指针和慢指针都变成“每次走一步”，继续前进。
4. 它们再次相遇的位置，就是环的入口。

第一次相遇后的操作，很多人会背，但不知道为什么。如果不把数学推导捋清楚，面试时一旦被追问“为什么重新走就能找到入口”，很容易卡壳。

5.2 相遇证明与入口推导：把字母设清楚，一切都顺了

先定义几个变量，然后推导。画一张图配合理解是最好的，我这里用文字描述：

• a：从链表头到环入口的距离，也就是无环部分的长度；
• b：从环入口到第一次相遇点的距离；
• c：从第一次相遇点继续走到环入口的距离；
• L：环的长度，显然 L = b + c。

慢指针从 head 出发，到第一次相遇一共走了 a + b 步。快指针同样从 head 出发，但因为它速度是慢指针的 2 倍，所以快指针走了 2(a + b) 步。另一方面，快指针进入环之后可能已经绕了好几圈才追上慢指针，假设它从进入环到第一次相遇，在环上兜了 k 圈，那么快指针走的路程也可以写成 a + b + kL。

于是得到方程：

2(a + b) = a + b + kL

化简一下就是：

a + b = kL

也就是说，从 head 到相遇点的距离，恰好等于 k 圈环的长度。再往下推：

a = kL - b = (k - 1)L + (L - b) = (k - 1)L + c

这个式子是什么意思？一个指针 P1 从 head 出发走 a 步，会到达环入口。另一个指针 P2 从第一次相遇点出发走同样的 a 步，它会绕环走 (k - 1) 圈，再多走 c 步。因为 L - b = c，多走 c 步正好让它从相遇点回到环入口。

所以当 P1 和 P2 以相同的速度同步前进时，P1 到达入口的那一刻，P2 也恰好到达入口，两个指针就在这里相遇。这就是第二步把快指针放回 head、再同步走就能找到入口的原因。

5.3 快指针为什么是 2 步不是 3 步，以及我踩过的边界坑

先回答一个常见疑问：快指针为什么每次走 2 步？3 步不行吗？

技术上，快指针只要比慢指针快就能追上，但每次走 2 步有一个特别好的性质：快指针相对慢指针的速度是 1 步，也就是说，每走一轮，快指针和慢指针之间的距离缩短 1，它不会“跳过”慢指针。如果快指针每次走 3 步，速度差是 2，那么当两者距离只有 1 时，快指针可能直接从慢指针头上跨过去，导致“擦肩而过”。虽然继续追也可能再追上，但证明和实现都变复杂了。所以工程上选 2 步，不是唯一解，是最省事的解。

再提醒一个非常容易踩的边界坑。快指针每次走两步，所以循环条件必须同时检查fast和fast.next都不为 None：

def detectCycle(head): fast = slow = head while fast and fast.next: fast = fast.next.next slow = slow.next if fast is slow: fast = head while fast is not slow: fast = fast.next slow = slow.next return fast return None

如果链表只有一个节点，fast.next是 None，循环不会进入，直接返回 None，说明无环。如果链表有两个节点且形成环，fast和fast.next都有效，循环能正常进入。很多人在这个边界上写错，是因为只检查了fast不为空，结果在取fast.next.next时对 None 调用属性，直接崩溃。

还有一点，慢指针进入环之后，快指针一定能在慢指针走完一圈之前追上它。因为快指针相对慢指针的速度是 1，而两者在环上的初始距离一定小于环长，所以追赶所需的步数也小于环长。这个性质保证了第一次相遇一定发生，而不是快指针永远追不上。

6. 四道题做下来，我的链表“手感”发生了什么变化

做完这四道题，我回头看了一下前两天的自己，发现最大的变化不是“多会了四道题”，而是开始习惯在动手写代码之前，先问自己三个问题：

1. 这步操作会改动哪些节点的 next？
2. 这些节点的引用，之后还需要用到吗？
3. 如果链表为空、只有一个节点、要处理头节点，我的代码会走到哪条分支？

这三个问题听起来简单，但真正形成条件反射，需要足够的练习。Day04 的四道题刚好把这三个问题的答案全部覆盖了一遍：两两交换逼着你提前保存引用；删除倒数第 N 个节点逼着你考虑头节点边界；链表相交逼着你思考“节点对象”和“节点值”的区别；环形链表 II 逼着你用数学而不是直觉来判断算法的正确性。

如果你现在还在卡其中某一道题，我的建议是：先别急着看题解，拿一张纸，画出链表结构，把每一步修改指针都标出来，然后对着图念一遍“现在这一步改的是谁，原来指向谁，改完后指向谁”。念不通的地方，就是你的理解漏洞。我试过很多次，这个方法比盯着代码看半小时有效得多。

另外，所有链表题都可以准备一套固定的测试用例集：空链表、单节点链表、头节点需要被操作的情况、尾节点需要被操作的情况、两个节点组成的链表。每道题写完，先用这套用例跑一遍，再去判题系统提交。熟练之后你会发现，好多提交错误根本不用上系统，自己在本地就能发现。Day04 就是我链表手感真正成型的一天，希望你也能顺利跨过这道坎。