1. Day4 的起点：从数组转向链表的第一个坎

到了代码随想录训练营的第4天，大部分人的状态其实挺微妙的。数组那几道题刷完，双指针、滑动窗口、前缀和这些套路刚有点手感，结果今天一上来就要切链表，很多人第一天写反转链表的时候，指针指来指去，把自己绕晕了还不算，代码跑起来直接死循环——这种事太常见了。我当年也是这么过来的，所以这篇文章就专门把 Day4 的链表专项做一个完整的复盘，从理论到题目再到实战心得，一次讲透。

先对齐一下今天的内容范围。Day4 的典型安排是围绕链表这一章节展开的，核心考点落在反转链表、两两交换链表中的节点、删除链表的倒数第 N 个节点，以及环形链表这组题上。这四道题看着不多，但每一道都能延伸出一堆面试变形题，而且它们联合起来恰好覆盖了链表题里最核心的几个操作维度：指针重连、虚拟头节点、双指针快慢、数学推导。换句话説，只要你把今天这几道题吃透，后续再做链表相关的中等题，基础的思维模型就已经齐了。

我见过不少人刷链表题有一个共同的误区：上来就背题解，把 cur、pre、next 三个变量来回倒腾的代码背得滚瓜烂熟，但碰上稍微变一下的题目就完全不会了。原因很简单，链表操作的本质不是"背指针赋值顺序"，而是"理解每个节点在内存中的连接关系是怎么被改写的"。所以我会在今天的笔记里，先花一点篇幅把链表的基础结构讲清楚，再逐题拆解。这样后面不管题目怎么变，你手里有一把通用的钥匙。

2. 链表基础：为什么它和数组的思维模型完全不同

2.1 内存布局的差异，决定了写法的差异

数组在内存里是一段连续的空间，所以你可以通过下标直接算出某个元素的内存地址，访问是 O(1) 的。链表不同，每个节点是单独 new 出来的，节点之间靠指针串起来，内存里东一块西一块，你只能从头节点开始，一个一个 next 找过去，查找是 O(n) 的。

这个差异直接导致了一个结果：数组题里你习惯的"根据下标找元素"的思维方式，在链表题里行不通。链表的每一个操作都是"改指针"，不是"改数据"。比如你要删除第 3 个节点，数组题的做法是把后面所有元素往前搬移，链表题的做法是让第 2 个节点的 next 直接跳过第 3 个节点，指向第 4 个节点。数据没动，只是连接关系变了。

记住一个核心视角：链表题从头到尾都在处理"节点的 next 指向哪里"，不是在处理"节点里存了什么值"。

2.2 虚拟头节点：解决头节点被删/被改时的空指针问题

链表题里有一个出现频率极高的工具，叫虚拟头节点（dummy head）。为什么需要它？因为很多操作需要修改头节点本身，比如把第一个节点删掉，或者把新节点插到最前面。如果直接操作 head 指针，你会发现代码里要写一堆 if 判断来特判"当前操作的是不是头节点"，特判一多，边界就容易出错。

虚拟头节点的做法是：新建一个 dummy 节点，让 dummy.next 指向真实链表的头节点，然后所有操作都从 dummy 开始遍历，最后返回 dummy.next。这样头节点也被统一成了"普通节点"，所有节点都有一致的前驱，代码逻辑就干净很多。

我自己的习惯是：凡是涉及删除节点、反转链表、需要返回新头节点的题，一律先建 dummy。虽然有些题不建 dummy 也能写，但建了之后边界会好处理得多，尤其在面试现场紧张的时候，少一点边界特判就少一点翻车的概率。

2.3 指针操作的三个口诀

链表操作本质上就是三种关键动作：保存后继、断开重连、移动指针。这三个动作的先后顺序一旦错了，节点就会丢。

我做链表题时脑子里一直有这三句话：

• 先保存，再修改。修改一个节点的 next 之前，先把它原来的 next 保存下来，否则节点就找不到了。
• 画图，不脑补。链表题最忌讳脑子模拟，三步以上的指针操作一定要在纸上画出节点和箭头。
• 每个循环结束前，想清楚"循环变量怎么更新到下一步"，很多死循环就是这一步忘了。

这三句话看起来简单，但真正做到位的人不多。我见过太多人代码写得飞快，一跑起来直接报错，或者输出结果只有一半，原因基本都是违反了第一条或第三条。

3. 反转链表：Day4 的第一道分水岭

3.1 双指针思路与迭代实现

反转链表（LeetCode 206）是一道必须手撕到烂的题。题面很简单：给你一个单链表的头节点，把链表反转过来，返回新的头节点。但就是这道"入门题"，每年面试挂掉的人依然不少。

核心思路是这样的：遍历链表的过程中，把每个节点的 next 指针指向前一个节点。听起来很简单，但你直接改的话，链会断掉，因为你把当前节点的 next 指向前驱以后，就找不到原来的后继了。所以需要提前保存后继节点。

代码实现：我直接用 Python 写了一段当前我实际会用的版本：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head): pre = None cur = head while cur is not None: next_node = cur.next # 先保存下一个节点 cur.next = pre # 反转当前节点的指针 pre = cur # pre 前移 cur = next_node # cur 前移 return pre

我解释一下为什么最后返回 pre：循环结束时 cur 已经指向 None，pre 恰好停留在原链表的尾节点，而这个尾节点在反转后就是新链表的头节点。就这么简单。

很多人第一次写的时候容易犯一个错——忘了 next_node = cur.next 这一行。一旦忘记，cur.next = pre 执行完之后，原来的后半段链表就凭空丢了，代码输出只有两个节点。这个坑我当年也踩过，后来总结的原因就是：写代码之前没把"先保存后继"这个动作刻在脑子里。

3.2 递归写法：知其然也知其所以然

反转链表的递归写法，对于理解链表数据结构是很好的练习，面试偶尔也会有人问（主要是想看你的递归思维扎不扎实）。这里贴一个递归版本：

def reverse_list_recursive(head): if head is None or head.next is None: return head new_head = reverse_list_recursive(head.next) head.next.next = head head.next = None return new_head

理解的关键在于递归的"信任"：你调用 reverse_list_recursive(head.next)，要相信它会返回一条已经反转好的链表，并让原来的 head.next 成为这条新链表的尾节点。基于这个信任，我们只需要做两件事：让 head.next 的下一个节点指向 head（实现局部反转），再把 head.next 置空（切断旧连接）。递归跑到底层会把所有节点的 next 依次反转回来。

不过说实话，递归版本虽然代码更短，但可读性对大多数人并不友好。我实际的建议是：迭代版本必须烂熟于心，递归版本当作理解加深去练。面试里能用迭代解决就用迭代，省得解释递归栈的调用过程时把自己绕进去。

3.3 本地调试的技巧：如何用最小用例验证

链表题的调试比数组题麻烦，因为你不是直接 print 整个链表就行的。我常用的调试方式是写一个辅助函数，把链表转成列表打印出来：

def linked_list_to_list(head): result = [] cur = head while cur is not None: result.append(cur.val) cur = cur.next return result

然后就可以这样测试：

# 构造 1 -> 2 -> 3 -> 4 -> 5 head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))) result = reverse_list(head) print(linked_list_to_list(result)) # [5, 4, 3, 2, 1]

为什么强调这个？因为我观察到很多人在 LeetCode 上代码提交没问题，但你让他本地跑一下，他连怎么构造样例都不会。这样其实失去了一个很重要的自查手段。会写辅助函数、会构造链表测试用例，也是在训练对链表的肌肉记忆。

4. 两两交换链表中的节点：递归与迭代的双重体验

4.1 题目与"交换"的本质

两两交换链表中的节点（LeetCode 24）是 Day4 里另一道高频题。题意是：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯修改节点内部的值，而是需要实际进行节点交换。

我先说这道题最容易被忽略的考点——它考的不是"交换两个节点的值"，而是"调整指针让节点真正交换位置"。为什么不建议直接改 val？因为面试官想看的是你对链表指针结构的掌控能力，而且如果节点的 val 是一个很复杂的对象，交换 val 会有很大的开销和副作用。所以题设里面经常白纸黑字写着"不能只改 val"。

对于链表 [1, 2, 3, 4]，交换完应该是 [2, 1, 4, 3]，这个大家都能想到，但实现的时候很多人处理不好"交换之后如何把自己接到前一组的尾巴上"。换句话说，你要管的不只是相邻两个节点怎么互指，还有整个组的连接怎么衔接。

4.2 迭代解法：虚拟头节点 + 三步指针调整

这道题的迭代解法我推荐用 dummy 节点来统一处理，否则头节点和后面的节点逻辑不一致，你需要额外写特判。整体实现如下：

def swap_pairs(head): dummy = ListNode(0) dummy.next = head pre = dummy while pre.next is not None and pre.next.next is not None: first = pre.next second = pre.next.next # 第一步：first 指向 second 的下一个节点 first.next = second.next # 第二步：second 指向 first second.next = first # 第三步：pre 指向 second pre.next = second # 移动 pre：此时 first 已经变成了这一组的"尾部" pre = first return dummy.next

拆开看这三步其实挺好记忆的。假设当前链段是 pre -> first -> second -> rest：

• first.next = second.next，把 first 的先接到 rest 上，相当于让 second 脱离原来的后驱关系。
• second.next = first，让 second 反过来指向 first，局部相邻节点已经成功互换。
• pre.next = second，把前面已经处理好的部分接到新的组头 second 上。
• 最后 pre = first，因为在这一组里，first 变成了该组的最后一个节点，下一组要从它后面开始处理。

这个步骤里最容易出问题的就是第二步执行完之后，old pre.next 实际上还指向 first，如果不把 pre.next 更新为 second，整个链就串不起来。我建议你在草稿纸上画一下 pre、first、second 三个指针的位置变化，跟着代码走一遍，之后就完全理解了。

4.3 递归解法与链表递归的统一视角

既然讲了反转链表的递归写法，这道题的递归版本也顺带看一下，因为两者逻辑上不冲突，反而是同一个思路的不同表达：

def swap_pairs_recursive(head): if head is None or head.next is None: return head first = head second = head.next # 递归处理后面的一串 first.next = swap_pairs_recursive(second.next) # second 接管这一组的头节点位置 second.next = first return second

看到没有，核心还是那两步：先把当前组的后部分递归处理好，再接回当前组内部的指针。一旦你接受了"递归函数会帮你处理后面所有节点"这个假设，代码读起来就没有那么吓人了。

我发现很多人递归学不会，不是因为笨，而是因为不敢"信任"递归函数的返回值。其实你只要把递归函数当成一个已经写好的工具，它接收一个链头，返回一个处理完的链头，你只需要考虑"在它返回的结果上，我怎么把当前的局部接上去"——这就是所有链表递归题的通用套路。

4.4 一个日常练习建议：两种解法都要能写出来

我个人的建议是，刷题前期，可以先主攻迭代写法，因为面试里更快、更稳，不容易栈溢出。但中期一定要把递归版也练熟，因为有很多链表题（比如后面会遇到的合并链表、反转部分链表）用递归的思路去理解，其实很容易和分治、回溯等思维打通。两两交换这道题恰好提供了一个很好的练习机会——迭代和递归的代码都简单，但思维模式完全不同。一道题能逼你同时掌握两种解题武器，性价比很高。

5. 删除链表的倒数第 N 个节点：双指针与 dummy 的组合拳

5.1 为什么"两次遍历"不如"一次遍历"

删除链表的倒数第 N 个节点（LeetCode 19），题面也简单：给你一个链表，删除链表的倒数第 n 个节点，返回链表的头节点。

一个最直接的想法是：先遍历一遍，算出链表长度 L，然后走到第 L - n 个节点，把它的 next 指向下下个节点。这个思路没问题，但它用了两次遍历（第一次数长度，第二次找位置）。面试官通常会追问一句："能不能只遍历一次？"

这个追问背后的逻辑是考察你有没有掌握"快慢指针/双指针"的思想。链表的题目里，双指针能解决很多看似需要两次遍历的问题，比如查找倒数第 k 个节点、判断链表是否有环、寻找环的入口等。所以这道题是双指针应用在链表场景里的经典入门。

5.2 双指针解法详解

核心思路是让快指针先走 n 步，然后快慢指针同步前进。当快指针到达链表末尾（null）时，慢指针正好停在倒数第 n 个节点的前一个位置上。为什么是"前一个"？因为删除节点需要拿到它的前驱才能重连指针，而让慢指针在目标节点前一个位置停下，是最安全、最不需要特判的做法。

为了统一头节点被删的情况，依然建议加 dummy：

def remove_nth_from_end(head, n): dummy = ListNode(0) dummy.next = head fast = dummy slow = dummy # 快指针先走 n 步 for _ in range(n): fast = fast.next # 快慢指针同时前进，直到 fast 到达末尾 while fast.next is not None: fast = fast.next slow = slow.next # 此时 slow 指向待删除节点的前驱 slow.next = slow.next.next return dummy.next

注意这里 fast 和 slow 都从 dummy 开始走，而不是从头节点开始。这样当 n 恰好等于链表长度时（也就是要删除头节点），for 循环走完 n 次之后 fast 在 null 的前一个节点，快慢指针同步时 slow 恰好停在 dummy 处，slow.next = slow.next.next 等价于直接删掉了原来的头节点。这就是 dummy 的价值——不用特判。

这个解法的复杂度是 O(n) 时间和 O(1) 空间，相比两次遍历版本，只多了一个"思想升级"，代码量几乎没有增加。但在面试官眼里，能写出这种解法，说明你具备基本的双指针建模能力，之后考快慢指针判断链表环时，你至少是有基础的。

5.3 边界错误集合：n 的取值和空指针

这道题最容易翻车的边界条件有三个。我挨个说一下，都是我实际看到别人踩过的：

• n 等于链表长度时，删除的是头节点。如果你没有用 dummy，就需要写 if n == len(head) 这种特判，代码很容易变丑；用了 dummy 的话直接免掉。
• n 大于链表长度。题目一般会约束 n 在有效范围内，但你自己写测试用例的时候要养成先判断的习惯，省的调试时怀疑人生。
• 链表只有一个节点。这种最简单的 case，很多人反而写错。你画一下慢指针的位置就能发现，dummy 方案里 slow.next = slow.next.next 是安全的，因为 slow.next.next 是 None，赋给 slow.next 没有任何问题。

我建议这种边界题都一律写成测试函数跑一下，别靠眼睛去验证。比如构造长度分别为 1、2、n 的链表，分别删除不同的 n，把结果用辅助函数转成列表看看是否符合预期。

6. 环形链表：从哈希表到快慢指针，再聊数学推导

链表环问题一共有两道经典题：判断是否有环（LeetCode 141）和找到环的入口（LeetCode 142）。Day4 一般会把它们一起覆盖，我把它们合并来讲，因为两者思路是连贯的。

6.1 解法一：哈希表思路

最容易想到的办法是：遍历链表，把每个节点的引用存进哈希表。如果某个节点第二次出现，说明链表有环，而且这个节点就是环的入口。代码非常简单：

def has_cycle(head): seen = set() cur = head while cur is not None: if cur in seen: return True seen.add(cur) cur = cur.next return False

但这里有一个重要的细节：哈希表里存的是节点对象，不是节点的值。因为两个不同的节点可能有相同的值，只有对象引用才能唯一标识一个节点。在 Python 里，对象默认的 hash 是基于内存地址的，直接用没问题。

哈希表解法的优点是直观、好写、不易出错，缺点是空间复杂度是 O(n)。面试时作为第一方案的快速回答是没问题的，但一般面试官都会让你继续优化到 O(1) 空间。

6.2 解法二：快慢指针 + Floyd 判圈

快慢指针的思路是：slow 每次走一步，fast 每次走两步。如果链表无环，fast 会先走到末尾；如果有环，fast 最终会在环里追上 slow，因为它们进入了同一个循环赛道，而 fast 的步幅更大。

写成代码：

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

这个解法是 O(n) 时间、O(1) 空间。面试中这个方案几乎是必须掌握的标准答案。有一点你可能纠结过的问题：slow 进环之后会不会永远遇不到 fast？答案是不会。假设它们在环里同一方向奔跑，fast 每走两步、slow 走一步，对应的，fast 相对于 slow 每次靠近一个节点。环的长度是有限的，所以追逐必能在有限步内完成。

6.3 题 142 的数学推导：为什么快指针走后，两指针相遇点到环入口的距离等于头节点到环入口的距离

判断有环只是第一步。LeetCode 142 进一步要求"返回环的入口节点"。用快慢指针找到相遇点之后，还需要一个数学推导来定位入口。

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

相遇时：slow 走了 a + b 步；fast 走了 a + b + k*c 步，其中 k 是 fast 在环内多绕的圈数。由于 fast 速度是 slow 的两倍，所以：

2 * (a + b) = a + b + kc
=> a + b = kc
=> a = k*c - b

这个式子如果不直观，可以换个角度想：a 恰好等于从相遇点继续走（k-1）圈再走 c - b 的距离。也就是説，如果一个人从相遇点出发，另一个人从头节点出发，两人以相同速度前进，他们最终会在环入口相遇。

所以算法是：找到快慢指针的相遇点后，令 fast 回到 head，slow 留在相遇点，两者都改为每次走一步，再次相遇的位置就是环的入口。

def detect_cycle(head): slow = head fast = head # 找到相遇点 while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow == fast: # 找环入口 fast = head while fast != slow: fast = fast.next slow = slow.next return fast return None

坦白说，这个推导我当年第一次看的时候也绕了好一会儿。我建议你在草稿纸上把 a、b、c 标出来，代入几个具体数字（比如 a=2, b=1, c=4）验证一下，就彻底通了。数学符号看不进去没关系，代入数字算一遍比什么都管用。

6.4 环类题目在面试中的延展

环形链表还经常和其他知识点结合起来考。常见的延展有：找到环的长度（相遇后继续跑一圈数步数）、删除环（把环打断）、多条链相交问题（本质上也可以转换成环来做）。多练一组这两道题，后面遇到这些变体至少不会懵。

7. 链表题的通用套路与刷题规划建议

7.1 四条通用心法

把 Day4 的链表题做完，你会发现它们其实共享同一套底层思维。我梳理了四条对自己的刷题帮助很大的"通用心法"：

第一，先判断是否需要 dummy。凡是涉及头节点可能被修改、删除、移动的题目，优先考虑虚拟头节点。它不会增加时间和空间复杂度，却能把代码从一堆 if 里解放出来。第二，先保存后继再改指针。这是链表题所有错误的头号来源，写代码前默念一遍。第三，画图。任何指针操作三步以上，不要吝啬纸笔，画错也比空想好。第四，除非题目明确禁止，否则优先返回 dummy.next 而不是 head。因为你可能在操作过程中改变了 head 的指向，直接用原 head 很容易出错。

7.2 刷题顺序与时间分配

Day4 的题如果第一次接触，我建议按这个顺序来：

• 先做 206 反转链表，因为它是最基础的指针重连操作，也是后续所有题的地基。
• 再做 24 两两交换节点，因为它可以在反转链表的基础上，练习多组节点之间的衔接。
• 接着做 19 删除倒数第 N 个节点，让你彻底理解双指针和 dummy 的配合。
• 最后看 141 和 142 环形链表，因为它们还需要一点数学推导，放在最后消化压力小。

时间分配上，每道题第一次写建议控制在 30 到 45 分钟。如果超过 45 分钟还没思路，直接看题解，看完之后关上答案自己重写一遍。不要恋战，但也不要"背答案式"地刷过去。关键在于看完题解后的那一遍独立重写，才是真正内化的过程。

7.3 二刷需要注意的事情

这些人题目如果只刷一遍，几天后必定会忘。我做了三轮刷题之后，发现二刷最值得做的不是重新把代码敲一遍，而是做三件事：不看代码，在纸上画出每道题的指针变动过程；对比迭代和递归写法，总结各自适合的场景；把所有题目的易错点整理成一份清单，下次面试前只看清单不看代码。

链表题一个很有意思的地方是：题量很少，套路很固定。相比动态规划动辄几百道题的量级，链表核心题也就是那么十几个。集中时间搞定了，后面几乎是"吃老本"状态。Day4 是打链表基础最关键的一天，这四类题过完，后面的链表作业题大概率都能举一反三。

我在实际操作中还有一个体会：别急着追求"最优解优先"。自己写的时候，只要能 AC，先用能想到的解法，比如哈希表的思路，然后再要求自己想一下怎么优化到 O(1) 空间。这个过程本身比直接背最优解重要得多。等到二刷的时候，你就可以强制自己只写最优解了。