连着刷了两天数组和哈希表第三天题目下来一看——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 - 6val是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(nexthead) 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跳过它。我自己在做联调测试时一般会准备这么几组用例用例输入预期输出说明空链表headNone, val1None直接返回删除头节点1-2, val12验证dummy的作用删除尾节点1-2-3, val31-2验证cur走到最后的边界连续删除1-2-2-3, val21-3验证prev不移动的逻辑全删光1-1, val1None验证返回空链表跑完这五组用例代码基本就稳了。时间复杂度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是负数头插可以视为index0的插入这个题目通常允许有些版本会特殊说明。这些边界不搞清楚代码写一半就会开始怀疑自己。我建议先读题时就把这些约束用注释写在类定义上方省的写到后面还要翻回去看。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长度。有了sizeaddAtTail和deleteAtIndex的边界判断就非常直观class ListNode: def __init__(self, val0, nextNone): 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个一组反转在递归解法里会用到同样的思想。如果你还处于“背代码”的阶段我特别推荐一个练习方法拿纸笔画出head1-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逼你用两种思维把链表重新理解一遍。从“删”到“管”再到“翻”刚好是一个链表能力爬坡的完整路径。这三题做完我不仅会写了更重要的是知道了链表题该往哪个方向想。如果你也在刷这道题建议按这个顺序一步步过代码写完再用那五个边界用例跑一遍链表这道关就算正式跨过去了。