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, val0, nextNone): 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 已经指向 Nonepre 恰好停留在原链表的尾节点而这个尾节点在反转后就是新链表的头节点。就这么简单。很多人第一次写的时候容易犯一个错——忘了 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 - restfirst.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 个节点的前一个位置上。为什么是前一个因为删除节点需要拿到它的前驱才能重连指针而让慢指针在目标节点前一个位置停下是最安全、最不需要特判的做法。为了统一头节点被删的情况依然建议加 dummydef 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 回到 headslow 留在相遇点两者都改为每次走一步再次相遇的位置就是环的入口。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 标出来代入几个具体数字比如 a2, b1, c4验证一下就彻底通了。数学符号看不进去没关系代入数字算一遍比什么都管用。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) 空间。这个过程本身比直接背最优解重要得多。等到二刷的时候你就可以强制自己只写最优解了。