连着刷了两天数组和哈希表，第三天题目下来一看——203.移除链表元素、707.设计链表、206.反转链表。说实话，看到“链表”两个字我是有点慌的，数组好歹能用下标走天下，链表这玩意儿的指针和节点关系，在脑子里转着转着就容易把自己绕进去。但把这三道题完整做下来之后，我反倒觉得链表比数组“诚实”多了：它把每一步操作的代价都摆在明面上，你要改哪条指针、断哪条连接，画清楚了就一定能写对。这篇文章就把我第三天的完整做题过程、踩过的坑、以及从三道题里总结出来的通用套路整理出来，给同样在啃链表的朋友做个参考。1. 链表题难在哪：先搞懂“节点”和“指针”的关系1.1 为什么算法训练营要把链表放在第三天数组和哈希表解决的是“快速存取”的问题，而链表解决的是“频繁插入删除”的问题。两者是互补的基础数据结构。数组的删除，最坏情况要把后面所有元素往前挪，时间复杂度是O(n)，而链表删除一个节点，只需要改两条指针的指向，O(1)就能完成——前提是你已经站在了要删的那个节点旁边。链表题之所以劝退新手，我个人觉得核心原因有两个：第一，链表没有“下标”这个概念。你没办法直接跳到第k个节点，只能从头节点开始一个一个next走过去，这就是“链式访问”的本质。很多初学者写链表代码时还带着数组思维，总想直接访问某个位置，结果越写越别扭。第二，空指针风险无处不在。访问cur.next的前提是cur不为空，删除节点时还要保证prev.next存在。在纸上画图的时候一切都合理，一写成代码就各种NoneType报错。所以训练营把这个顺序安排得挺讲究：前两天的数组和哈希表解决的是“数据怎么存”，第三天开始用链表解决“数据怎么改”。题目难度是递进的，203是最基础的删除操作，707是一道综合设计题把增删改查全考了一遍，206则从操作层面上升到思维层面（递归和迭代两种思路）。三道题做完，链表的基本功基本就夯实了。1.2 虚拟头节点：一个让所有边界消失的小技巧如果让我只用一个词概括第三天最大的收获，我会选“虚拟头节点”（dummy node）。这个东西在链表中太常用了，但这三道题里体现得尤其充分。虚拟头节点的思路很简单：在处理链表时，额外创建一个节点，它的next指向真正的头节点head，然后所有操作都从这个虚拟节点出发。这样做的直接好处是——头节点不再是“特殊节点”。举个最直白的例子。删除链表中值为val的节点，如果用常规思路，你需要判断“当前节点是不是头节点”，因为删除头节点和删除中间节点走的是两套逻辑：删除头节点时要更新head，删除中间节点时要改前一个节点的next。一个题目里出现两套分支，就特别容易漏。而有了虚拟头节点，头节点和其他节点在操作上完全一样，最后只要返回dummy.next就行。这个技巧在203、707、206三题里全部适用。可以说，掌握了虚拟头节点，链表题的正确率能直接上一个台阶。1.3 链表操作的三个基本动作：删、插、翻第三天的三道题表面上是三道独立题目，本质上是链表操作的三类基本动作：删除（203）：让前一个节点绕过待删除的节点，指向它的下一个节点。核心是“谁跳过谁”。插入（707）：新节点的next先指向后一个节点，前一个节点的next再指向新节点。核心是“先后再前”，顺序反了链表就断了。反转（206）：把每个节点的next方向调头，同时让原来的头变尾。核心是“保存下一个节点之后再改指针”。这三类动作合起来，就是链表操作的全部家当。后文我会按做题顺序，把每一道题从读题到实现再到边界测试从头到尾拆一遍。2. 203.移除链表元素：删除操作里的“谁跳过谁”逻辑2.1 题目要什么：把所有等于目标值的节点从链上拆下来203题的要求很直接：给定一个链表的头节点head和一个整数val，删除链表中所有值为val的节点，并返回新的头节点。举个例子，链表是1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6，val是6，删除之后应该是1 -> 2 -> 3 -> 4 -> 5。注意里面有两个6，一个在中间，一个在结尾，都要删干净。这道题我一开始没写虚拟头节点，直接上手用双指针prev和cur去移动，结果在删除头节点这个场景上卡了半天。头节点的值是6时，你压根没有prev可以改，只能把head往后挪。代码写着写着就变成了：# 先处理头节点是目标值的情况 while head and head.val == val: head = head.next # 再处理中间节点 prev, cur = head, head.next if head else None这一版虽然在逻辑上没错，但代码的可读性很差，后面加需求、改逻辑都费劲。我后来还是删掉重写，老老实实用了虚拟头节点。2.2 不写虚拟头节点时，连续删除有多痛苦这里我想多说一句连续删除的情况，这是最容易踩的坑。比如链表是1 -> 2 -> 2 -> 3，要删除所有值为2的节点。如果你在循环里同时移动prev和cur，第一次删除第一个2之后，prev还在1的位置，cur已经指向第二个2，这时候如果继续同时移动，prev就会变成第一个2（它还在链表里呢），逻辑立刻乱套。正确的处理方式是：cur每次都要移动，但prev只在没有发生删除的时候才移动。只有这样才能保证prev始终指向最后一个“保留节点”，从而可以把后面所有连续的目标值都跳过去。这也是写链表删除时一个非常重要的细节。2.3 完整实现与测试用例：dummy节点方案用虚拟头节点写出来的代码非常干净：class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: dummy = ListNode(next=head) prev, cur = dummy, head while cur: if cur.val == val: prev.next = cur.next else: prev = cur cur = cur.next return dummy.next这个版本的核心思路就一句话：cur负责探路，prev负责保留合法节点，发现cur是目标值，就让prev.next跳过它。我自己在做联调测试时，一般会准备这么几组用例：用例输入预期输出说明空链表head=None, val=1None直接返回删除头节点1->2, val=12验证dummy的作用删除尾节点1->2->3, val=31->2验证cur走到最后的边界连续删除1->2->2->3, val=21->3验证prev不移动的逻辑全删光1->1, val=1None验证返回空链表跑完这五组用例，代码基本就稳了。时间复杂度O(n)，空间复杂度O(1)，链表删除类题目的最优解。2.4 容易翻车的三个细节返回值一定是dummy.next，不是head。因为原来的head可能已经被删掉了。这一步我一开始就写错过，head指向被删除节点时，返回head直接就错了。cur = cur.next的位置不能省。代码里cur每次循环都往后走，不加这一行就死循环了。另外cur是独立的“探针”，不会因为prev.next被修改而丢失。如果用的是C++这类需要手动管理内存的语言，删除节点后记得free。这道题在训练营的代码模板里，C++解法会有一个tmp指针先保存要释放的节点，再改prev.next，否则内存就泄漏了。写Python时没有这个烦恼，但思路要懂。203这道题本身不难，但它是所有链表操作题的地基。把“谁跳过谁”想清楚，后面的707和206就会顺很多。3. 707.设计链表：一道综合题把“增删改查”全部串起来3.1 先读题：五个方法背后的索引语义707题不给你现成的链表，而是让你自己实现一个链表类。它的要求有五个方法：get(index)获取指定索引的节点值、addAtHead(val)头插、addAtTail(val)尾插、addAtIndex(index, val)在指定索引插入、deleteAtIndex(index)删除指定索引节点。读题阶段最容易忽视的是题目对索引边界的规定。我记得题目里明确说了几点：索引从0开始；addAtIndex中，如果index等于链表长度，表示添加到链表末尾，是合法的；如果index大于链表长度，则插入无效；如果index是负数，头插可以视为index=0的插入，这个题目通常允许（有些版本会特殊说明）。这些边界不搞清楚，代码写一半就会开始怀疑自己。我建议先读题时就把这些约束用注释写在类定义上方，省的写到后面还要翻回去看。3.2 addAtIndex是核心：所有插入操作都归到它我实现这题时，发现没必要把addAtHead和addAtTail单独写逻辑。用addAtIndex(index, val)统一处理，addAtHead就是addAtIndex(0, val)，addAtTail就是addAtIndex(size, val)。唯一的坑是索引偏移的理解。链表有dummy节点时，addAtIndex(index, val)你需要找到第index个节点的前驱。那从dummy出发要走多少步？答案是index步。因为dummy在“-1”的位置，走0步到dummy自己，走1步到原head（索引0），走index步正好到索引index-1的节点，也就是插入位置的前驱。这一步想明白，整道题就跟打通了任督二脉一样。3.3 完整实现：size、dummy和尾插条件如何配合链表类里面我维护了两个成员：dummy哨兵节点和size长度。有了size，addAtTail和deleteAtIndex的边界判断就非常直观：class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class MyLinkedList: def __init__(self): self.dummy = ListNode() self.size = 0 def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 cur = self.dummy.next for _ in range(index): cur = cur.next return cur.val def addAtHead(self, val: int) -> None: self.addAtIndex(0, val) def addAtTail(self, val: int) -> None: self.addAtIndex(self.size, val) def addAtIndex(self, index: int, val: int) -> None: if index < 0 or index > self.size: return prev = self.dummy for _ in range(index): prev = prev.next new_node = ListNode(val) new_node.next = prev.next prev.next = new_node self.size += 1 def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return prev = self.dummy for _ in range(index): prev = prev.next prev.next = prev.next.next self.size -= 1这个实现最需要注意的地方是addAtIndex里先new_node.next = prev.next，再prev.next = new_node的顺序。如果把这两行颠倒，先是prev.next指向了new_node，那原来后面那段链表就丢了，new_node.next想指向它也找不回来了。这个顺序问题在插入类操作里是最高频的错误，没有之一。3.4 我在这题上踩过的坑写这道题的时候，我在一个细节上卡了很久：addAtIndex的边界。一开始我把判断写成if index > self.size，漏掉了等于的情况。结果addAtTail调用addAtIndex(self.size, val)时，直接被return掉了，尾插永远失败。后来打印日志才发现，index == self.size是合法的尾插场景，必须写成if index < 0 or index > self.size: return。另一个坑是get的返回。题目要求索引无效时返回-1，但很多人会忘记判断负数。负数索引的情况在测试用例里很常见，比如测试空链表get(0)、测试负数get(-1)，这两条都是容易翻车的位置。写的时候先把这些边界case列出来再动笔，会稳很多。707这道题的价值不在于算法有多难，而在于它要求你在一个类里面统筹五六个方法的状态一致性。size必须在每次增删时同步更新，dummy必须始终存在，get和delete的索引判断必须和addAtIndex保持一致。这基本就是一轮小型的代码严谨性训练，面试手写链表题的时候经常能看到它的影子。4. 206.反转链表：迭代和递归是两种思考方式4.1 迭代法：三个指针的接力赛反转链表这个大题，题目描述同样简单：给你单链表的头节点head，反转链表，返回反转后的新头节点。先说我推荐大家都掌握的迭代写法：class Solution: def reverseList(self, head: ListNode) -> ListNode: prev, cur = None, head while cur: temp = cur.next cur.next = prev prev = cur cur = temp return prev这段代码看着短，很多人背得很熟，但问一句“为什么循环里要先保存temp”就答不上来了。原因很简单：cur.next = prev这一步会把cur原来的next覆盖掉，如果不先存下来，后面再也找不到原来的下一个节点了。所以temp = cur.next必须在改指针之前执行。这是反转操作和删除、插入操作不太一样的地方：删除是在“前一个节点”上做文章，反转则是直接在“当前节点”身上动手，必须先给自己留好退路。整个迭代过程可以用一个比喻来记：你在一列火车上从前往后走，每走到一节车厢，就把它的车钩从前一个方向改成指向后一个方向，同时手里攥着原本挂在后面那节车厢的钥匙（temp），保证你不会在改车钩之后迷路。等走完全程，pre所在的位置正好就是新头节点。4.2 递归法：先信“后面的已经反转好了”递归写法我一开始是完全懵的，后来换了一种思考方式才彻底理解。先看代码：class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head new_head = self.reverseList(head.next) head.next.next = head head.next = None return new_head核心就在head.next.next = head这一行。怎么理解？你要无条件地相信递归调用返回之后，head.next这个节点以及它后面的所有链表已经反转好了。所以现在的局面是：head指向head.next，而head.next后面的那一整段已经完成了反转，并且反转后那一段的最后一个节点恰好是head.next（别绕晕，反转后原来的尾部变成了头部，原来的头部变成了尾部，也就是head.next）。那head该做什么？它只需要把这根“新尾部”和head自己连起来：head.next.next = head，也就是让原链表的第二个节点（现在是反转后的最后一个节点）的next指向head。最后别忘了head.next = None，否则链表成环，这是递归解法里非常容易被忽略的一步。4.3 两种思路如何选择与记忆迭代和递归的区别，我用一个表格总结一下：对比项迭代递归空间复杂度O(1)O(n)，递归栈深度理解难度直观，适合新手递推关系抽象，需要信任出错点忘记保存temp忘记把head.next置None面试推荐优先掌握能讲清楚是加分项我的建议是：迭代法必须做到闭眼能写，因为它在面试中最高频，而且空间复杂度更优。递归法至少要把“相信后面已反转 + head.next.next = head”这层逻辑理解透，因为很多复杂链表题（比如反转链表的一部分、K个一组反转）在递归解法里会用到同样的思想。如果你还处于“背代码”的阶段，我特别推荐一个练习方法：拿纸笔，画出head=1->2->3这个例子，递归调用手工展开。你会发现递归到最后一层返回的是3，然后逐层返回时分别把2的next指向1、把3的next指向2，最终返回的new_head一直是3。走完一遍，比看十遍题解都管用。5. 从三道题提炼链表通用方法论5.1 画图定位问题，比盯着代码更有效三天的训练让我一个特别深的体会：链表题，纸和笔比编译器更先跑通代码。很多错误如果直接用肉眼看代码是看不出来的，但只要把链表画出来，一个一个节点标上指针方向，立刻就能发现问题出在哪一步。我现在的习惯是：每道链表题动笔前，先画一个最少三个节点的链表，比如A -> B -> C，然后把自己要操作的那几条指针用不同颜色标出来。删除就标“谁跳过谁”，插入就标“新节点先连谁再连谁”，反转就标“每个节点的next从哪里指到哪里”。画完了再写代码，基本一遍过。这个习惯对后面的双链表、循环链表同样适用。5.2 边界条件五件套：每次写链表题先过一遍刷完这三道题，我发现链表题有一个通行的边界检查清单，每次写前先过一遍能省大量调试时间：空链表：head为None时，循环进不进？返回值是什么？单节点链表：只有1个节点时，操作后head会不会变？指向对不对？删除头节点/在头部插入：需不需要特殊处理？dummy方案能不能统一？删除尾节点/在尾部插入：cur走到最后时，next操作有没有越界？连续相同值：链表里连续出现多个目标值时，删除逻辑能不能覆盖？任何一道链表题，把上面五条想清楚，代码都不会出大问题。这个清单我在做203和707时反复用，正确率提升非常明显。5.3 复杂度分析与面试扩展思路三道题的复杂度都很直观：203和206都是时间复杂度O(n)、空间复杂度O(1)（递归除外）；707的get、addAtIndex、deleteAtIndex也都是O(n)，因为需要从dummy出发遍历到目标位置，addAtHead在dummy直接后面插入，时间复杂度O(1)，addAtTail因为维护了size但仍需遍历到末尾，时间复杂度O(n)。面试如果追问，通常会往这几个方向延展：如何用双指针找中间节点、如何判断链表是否有环、如何反转链表的指定区间、如何用链表实现LRU缓存。这些进阶题的核心还是在第三天的基本功上做组合：虚拟头节点、prev/cur双指针、保存下一个节点再改指针。把这三板斧练熟，后面的题就不那么吓人了。回到第三天本身，我个人认为训练营这样设计题目是有内在逻辑的：203教你把最常用的删除操作做规范，707让你把所有操作串起来写一遍严谨的类，206逼你用两种思维把链表重新理解一遍。从“删”到“管”再到“翻”，刚好是一个链表能力爬坡的完整路径。这三题做完，我不仅会写了，更重要的是知道了链表题该往哪个方向想。如果你也在刷这道题，建议按这个顺序一步步过，代码写完再用那五个边界用例跑一遍，链表这道关就算正式跨过去了。
连着刷了两天数组和哈希表，第三天题目下来一看——203.移除链表元素、707.设计链表、206.反转链表。说实话，看到“链表”两个字我是有点慌的，数组好歹能用下标走天下，链表这玩意儿的指针和节点关系，在脑子里转着转着就容易把自己绕进去。但把这三道题完整做下来之后，我反倒觉得链表比数组“诚实”多了：它把每一步操作的代价都摆在明面上，你要改哪条指针、断哪条连接，画清楚了就一定能写对。这篇文章就把我第三天的完整做题过程、踩过的坑、以及从三道题里总结出来的通用套路整理出来，给同样在啃链表的朋友做个参考。1. 链表题难在哪：先搞懂“节点”和“指针”的关系1.1 为什么算法训练营要把链表放在第三天数组和哈希表解决的是“快速存取”的问题，而链表解决的是“频繁插入删除”的问题。两者是互补的基础数据结构。数组的删除，最坏情况要把后面所有元素往前挪，时间复杂度是O(n)，而链表删除一个节点，只需要改两条指针的指向，O(1)就能完成——前提是你已经站在了要删的那个节点旁边。链表题之所以劝退新手，我个人觉得核心原因有两个：第一，链表没有“下标”这个概念。你没办法直接跳到第k个节点，只能从头节点开始一个一个next走过去，这就是“链式访问”的本质。很多初学者写链表代码时还带着数组思维，总想直接访问某个位置，结果越写越别扭。第二，空指针风险无处不在。访问cur.next的前提是cur不为空，删除节点时还要保证prev.next存在。在纸上画图的时候一切都合理，一写成代码就各种NoneType报错。所以训练营把这个顺序安排得挺讲究：前两天的数组和哈希表解决的是“数据怎么存”，第三天开始用链表解决“数据怎么改”。题目难度是递进的，203是最基础的删除操作，707是一道综合设计题把增删改查全考了一遍，206则从操作层面上升到思维层面（递归和迭代两种思路）。三道题做完，链表的基本功基本就夯实了。1.2 虚拟头节点：一个让所有边界消失的小技巧如果让我只用一个词概括第三天最大的收获，我会选“虚拟头节点”（dummy node）。这个东西在链表中太常用了，但这三道题里体现得尤其充分。虚拟头节点的思路很简单：在处理链表时，额外创建一个节点，它的next指向真正的头节点head，然后所有操作都从这个虚拟节点出发。这样做的直接好处是——头节点不再是“特殊节点”。举个最直白的例子。删除链表中值为val的节点，如果用常规思路，你需要判断“当前节点是不是头节点”，因为删除头节点和删除中间节点走的是两套逻辑：删除头节点时要更新head，删除中间节点时要改前一个节点的next。一个题目里出现两套分支，就特别容易漏。而有了虚拟头节点，头节点和其他节点在操作上完全一样，最后只要返回dummy.next就行。这个技巧在203、707、206三题里全部适用。可以说，掌握了虚拟头节点，链表题的正确率能直接上一个台阶。1.3 链表操作的三个基本动作：删、插、翻第三天的三道题表面上是三道独立题目，本质上是链表操作的三类基本动作：删除（203）：让前一个节点绕过待删除的节点，指向它的下一个节点。核心是“谁跳过谁”。插入（707）：新节点的next先指向后一个节点，前一个节点的next再指向新节点。核心是“先后再前”，顺序反了链表就断了。反转（206）：把每个节点的next方向调头，同时让原来的头变尾。核心是“保存下一个节点之后再改指针”。这三类动作合起来，就是链表操作的全部家当。后文我会按做题顺序，把每一道题从读题到实现再到边界测试从头到尾拆一遍。2. 203.移除链表元素：删除操作里的“谁跳过谁”逻辑2.1 题目要什么：把所有等于目标值的节点从链上拆下来203题的要求很直接：给定一个链表的头节点head和一个整数val，删除链表中所有值为val的节点，并返回新的头节点。举个例子，链表是1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6，val是6，删除之后应该是1 -> 2 -> 3 -> 4 -> 5。注意里面有两个6，一个在中间，一个在结尾，都要删干净。这道题我一开始没写虚拟头节点，直接上手用双指针prev和cur去移动，结果在删除头节点这个场景上卡了半天。头节点的值是6时，你压根没有prev可以改，只能把head往后挪。代码写着写着就变成了：# 先处理头节点是目标值的情况 while head and head.val == val: head = head.next # 再处理中间节点 prev, cur = head, head.next if head else None这一版虽然在逻辑上没错，但代码的可读性很差，后面加需求、改逻辑都费劲。我后来还是删掉重写，老老实实用了虚拟头节点。2.2 不写虚拟头节点时，连续删除有多痛苦这里我想多说一句连续删除的情况，这是最容易踩的坑。比如链表是1 -> 2 -> 2 -> 3，要删除所有值为2的节点。如果你在循环里同时移动prev和cur，第一次删除第一个2之后，prev还在1的位置，cur已经指向第二个2，这时候如果继续同时移动，prev就会变成第一个2（它还在链表里呢），逻辑立刻乱套。正确的处理方式是：cur每次都要移动，但prev只在没有发生删除的时候才移动。只有这样才能保证prev始终指向最后一个“保留节点”，从而可以把后面所有连续的目标值都跳过去。这也是写链表删除时一个非常重要的细节。2.3 完整实现与测试用例：dummy节点方案用虚拟头节点写出来的代码非常干净：class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: dummy = ListNode(next=head) prev, cur = dummy, head while cur: if cur.val == val: prev.next = cur.next else: prev = cur cur = cur.next return dummy.next这个版本的核心思路就一句话：cur负责探路，prev负责保留合法节点，发现cur是目标值，就让prev.next跳过它。我自己在做联调测试时，一般会准备这么几组用例：用例输入预期输出说明空链表head=None, val=1None直接返回删除头节点1->2, val=12验证dummy的作用删除尾节点1->2->3, val=31->2验证cur走到最后的边界连续删除1->2->2->3, val=21->3验证prev不移动的逻辑全删光1->1, val=1None验证返回空链表跑完这五组用例，代码基本就稳了。时间复杂度O(n)，空间复杂度O(1)，链表删除类题目的最优解。2.4 容易翻车的三个细节返回值一定是dummy.next，不是head。因为原来的head可能已经被删掉了。这一步我一开始就写错过，head指向被删除节点时，返回head直接就错了。cur = cur.next的位置不能省。代码里cur每次循环都往后走，不加这一行就死循环了。另外cur是独立的“探针”，不会因为prev.next被修改而丢失。如果用的是C++这类需要手动管理内存的语言，删除节点后记得free。这道题在训练营的代码模板里，C++解法会有一个tmp指针先保存要释放的节点，再改prev.next，否则内存就泄漏了。写Python时没有这个烦恼，但思路要懂。203这道题本身不难，但它是所有链表操作题的地基。把“谁跳过谁”想清楚，后面的707和206就会顺很多。3. 707.设计链表：一道综合题把“增删改查”全部串起来3.1 先读题：五个方法背后的索引语义707题不给你现成的链表，而是让你自己实现一个链表类。它的要求有五个方法：get(index)获取指定索引的节点值、addAtHead(val)头插、addAtTail(val)尾插、addAtIndex(index, val)在指定索引插入、deleteAtIndex(index)删除指定索引节点。读题阶段最容易忽视的是题目对索引边界的规定。我记得题目里明确说了几点：索引从0开始；addAtIndex中，如果index等于链表长度，表示添加到链表末尾，是合法的；如果index大于链表长度，则插入无效；如果index是负数，头插可以视为index=0的插入，这个题目通常允许（有些版本会特殊说明）。这些边界不搞清楚，代码写一半就会开始怀疑自己。我建议先读题时就把这些约束用注释写在类定义上方，省的写到后面还要翻回去看。3.2 addAtIndex是核心：所有插入操作都归到它我实现这题时，发现没必要把addAtHead和addAtTail单独写逻辑。用addAtIndex(index, val)统一处理，addAtHead就是addAtIndex(0, val)，addAtTail就是addAtIndex(size, val)。唯一的坑是索引偏移的理解。链表有dummy节点时，addAtIndex(index, val)你需要找到第index个节点的前驱。那从dummy出发要走多少步？答案是index步。因为dummy在“-1”的位置，走0步到dummy自己，走1步到原head（索引0），走index步正好到索引index-1的节点，也就是插入位置的前驱。这一步想明白，整道题就跟打通了任督二脉一样。3.3 完整实现：size、dummy和尾插条件如何配合链表类里面我维护了两个成员：dummy哨兵节点和size长度。有了size，addAtTail和deleteAtIndex的边界判断就非常直观：class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class MyLinkedList: def __init__(self): self.dummy = ListNode() self.size = 0 def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 cur = self.dummy.next for _ in range(index): cur = cur.next return cur.val def addAtHead(self, val: int) -> None: self.addAtIndex(0, val) def addAtTail(self, val: int) -> None: self.addAtIndex(self.size, val) def addAtIndex(self, index: int, val: int) -> None: if index < 0 or index > self.size: return prev = self.dummy for _ in range(index): prev = prev.next new_node = ListNode(val) new_node.next = prev.next prev.next = new_node self.size += 1 def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return prev = self.dummy for _ in range(index): prev = prev.next prev.next = prev.next.next self.size -= 1这个实现最需要注意的地方是addAtIndex里先new_node.next = prev.next，再prev.next = new_node的顺序。如果把这两行颠倒，先是prev.next指向了new_node，那原来后面那段链表就丢了，new_node.next想指向它也找不回来了。这个顺序问题在插入类操作里是最高频的错误，没有之一。3.4 我在这题上踩过的坑写这道题的时候，我在一个细节上卡了很久：addAtIndex的边界。一开始我把判断写成if index > self.size，漏掉了等于的情况。结果addAtTail调用addAtIndex(self.size, val)时，直接被return掉了，尾插永远失败。后来打印日志才发现，index == self.size是合法的尾插场景，必须写成if index < 0 or index > self.size: return。另一个坑是get的返回。题目要求索引无效时返回-1，但很多人会忘记判断负数。负数索引的情况在测试用例里很常见，比如测试空链表get(0)、测试负数get(-1)，这两条都是容易翻车的位置。写的时候先把这些边界case列出来再动笔，会稳很多。707这道题的价值不在于算法有多难，而在于它要求你在一个类里面统筹五六个方法的状态一致性。size必须在每次增删时同步更新，dummy必须始终存在，get和delete的索引判断必须和addAtIndex保持一致。这基本就是一轮小型的代码严谨性训练，面试手写链表题的时候经常能看到它的影子。4. 206.反转链表：迭代和递归是两种思考方式4.1 迭代法：三个指针的接力赛反转链表这个大题，题目描述同样简单：给你单链表的头节点head，反转链表，返回反转后的新头节点。先说我推荐大家都掌握的迭代写法：class Solution: def reverseList(self, head: ListNode) -> ListNode: prev, cur = None, head while cur: temp = cur.next cur.next = prev prev = cur cur = temp return prev这段代码看着短，很多人背得很熟，但问一句“为什么循环里要先保存temp”就答不上来了。原因很简单：cur.next = prev这一步会把cur原来的next覆盖掉，如果不先存下来，后面再也找不到原来的下一个节点了。所以temp = cur.next必须在改指针之前执行。这是反转操作和删除、插入操作不太一样的地方：删除是在“前一个节点”上做文章，反转则是直接在“当前节点”身上动手，必须先给自己留好退路。整个迭代过程可以用一个比喻来记：你在一列火车上从前往后走，每走到一节车厢，就把它的车钩从前一个方向改成指向后一个方向，同时手里攥着原本挂在后面那节车厢的钥匙（temp），保证你不会在改车钩之后迷路。等走完全程，pre所在的位置正好就是新头节点。4.2 递归法：先信“后面的已经反转好了”递归写法我一开始是完全懵的，后来换了一种思考方式才彻底理解。先看代码：class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head new_head = self.reverseList(head.next) head.next.next = head head.next = None return new_head核心就在head.next.next = head这一行。怎么理解？你要无条件地相信递归调用返回之后，head.next这个节点以及它后面的所有链表已经反转好了。所以现在的局面是：head指向head.next，而head.next后面的那一整段已经完成了反转，并且反转后那一段的最后一个节点恰好是head.next（别绕晕，反转后原来的尾部变成了头部，原来的头部变成了尾部，也就是head.next）。那head该做什么？它只需要把这根“新尾部”和head自己连起来：head.next.next = head，也就是让原链表的第二个节点（现在是反转后的最后一个节点）的next指向head。最后别忘了head.next = None，否则链表成环，这是递归解法里非常容易被忽略的一步。4.3 两种思路如何选择与记忆迭代和递归的区别，我用一个表格总结一下：对比项迭代递归空间复杂度O(1)O(n)，递归栈深度理解难度直观，适合新手递推关系抽象，需要信任出错点忘记保存temp忘记把head.next置None面试推荐优先掌握能讲清楚是加分项我的建议是：迭代法必须做到闭眼能写，因为它在面试中最高频，而且空间复杂度更优。递归法至少要把“相信后面已反转 + head.next.next = head”这层逻辑理解透，因为很多复杂链表题（比如反转链表的一部分、K个一组反转）在递归解法里会用到同样的思想。如果你还处于“背代码”的阶段，我特别推荐一个练习方法：拿纸笔，画出head=1->2->3这个例子，递归调用手工展开。你会发现递归到最后一层返回的是3，然后逐层返回时分别把2的next指向1、把3的next指向2，最终返回的new_head一直是3。走完一遍，比看十遍题解都管用。5. 从三道题提炼链表通用方法论5.1 画图定位问题，比盯着代码更有效三天的训练让我一个特别深的体会：链表题，纸和笔比编译器更先跑通代码。很多错误如果直接用肉眼看代码是看不出来的，但只要把链表画出来，一个一个节点标上指针方向，立刻就能发现问题出在哪一步。我现在的习惯是：每道链表题动笔前，先画一个最少三个节点的链表，比如A -> B -> C，然后把自己要操作的那几条指针用不同颜色标出来。删除就标“谁跳过谁”，插入就标“新节点先连谁再连谁”，反转就标“每个节点的next从哪里指到哪里”。画完了再写代码，基本一遍过。这个习惯对后面的双链表、循环链表同样适用。5.2 边界条件五件套：每次写链表题先过一遍刷完这三道题，我发现链表题有一个通行的边界检查清单，每次写前先过一遍能省大量调试时间：空链表：head为None时，循环进不进？返回值是什么？单节点链表：只有1个节点时，操作后head会不会变？指向对不对？删除头节点/在头部插入：需不需要特殊处理？dummy方案能不能统一？删除尾节点/在尾部插入：cur走到最后时，next操作有没有越界？连续相同值：链表里连续出现多个目标值时，删除逻辑能不能覆盖？任何一道链表题，把上面五条想清楚，代码都不会出大问题。这个清单我在做203和707时反复用，正确率提升非常明显。5.3 复杂度分析与面试扩展思路三道题的复杂度都很直观：203和206都是时间复杂度O(n)、空间复杂度O(1)（递归除外）；707的get、addAtIndex、deleteAtIndex也都是O(n)，因为需要从dummy出发遍历到目标位置，addAtHead在dummy直接后面插入，时间复杂度O(1)，addAtTail因为维护了size但仍需遍历到末尾，时间复杂度O(n)。面试如果追问，通常会往这几个方向延展：如何用双指针找中间节点、如何判断链表是否有环、如何反转链表的指定区间、如何用链表实现LRU缓存。这些进阶题的核心还是在第三天的基本功上做组合：虚拟头节点、prev/cur双指针、保存下一个节点再改指针。把这三板斧练熟，后面的题就不那么吓人了。回到第三天本身，我个人认为训练营这样设计题目是有内在逻辑的：203教你把最常用的删除操作做规范，707让你把所有操作串起来写一遍严谨的类，206逼你用两种思维把链表重新理解一遍。从“删”到“管”再到“翻”，刚好是一个链表能力爬坡的完整路径。这三题做完，我不仅会写了，更重要的是知道了链表题该往哪个方向想。如果你也在刷这道题，建议按这个顺序一步步过，代码写完再用那五个边界用例跑一遍，链表这道关就算正式跨过去了。