今天聊链表刷题计划里的Day3。这三道题——203.移除链表元素、707.设计链表、206.反转链表——名字看着简单但刷过的人都知道它们是链表模块里最要命的“试金石”。很多人数组题做得飞起一到链表就卡壳原因很简单数组的操作有下标兜底链表全靠指针指来指去一个不小心就断链、丢节点、死循环。这篇文章不是贴三道题的答案而是把这三道题背后的东西彻底讲透为什么虚拟头节点能统一删除逻辑为什么707题看似简单却藏着大量边界为什么反转链表的迭代法三指针这么经典。无论是刚学数据结构的学生还是准备面试的求职者把这三道题吃透链表这块地基就稳了。1. 为什么Day3要同时刷这三道链表题1.1 链表学习的“最小闭环”链表这个数据结构的核心是两个词节点和指针。节点存数据指针把节点串起来。操作无非增、删、改、查但难就难在“改指针顺序这件事上不能有一点含糊”。我们常说要培养“指针感”其实就是大脑里能模拟出指针变化的动画效果。Day3这三道题刚好形成一个完整的能力闭环203是“删”——只改一个节点的next指向把目标节点从链条中摘除707是“建”——要实现完整的增删改查相当于把链表的每一种指针操作都过一遍206是“翻”——把所有相邻节点的指向全部逆过来是对指针操作的最高强度考验。我见过很多人看答案能看懂合上书自己写就崩本质问题就出在他只是在背代码没有建立对指针操作的心理模型。而这三道题恰好是建立心理模型的三个不同维度缺一个都不行。1.2 三道题如何层层递进从难度和思维量上看这三道题的递进关系很明显。203是最基础的“在遍历中改next”只需要维护一个prev指针思维上是线性的707开始涉及索引位置、边界判断、多种操作的统一处理难度一下就上来了206则完全转换视角你要在遍历的过程中“边走边重构”链表结构对空间想象能力的要求最高。更妙的是它们之间有天然的铺垫关系。203里你学会了虚拟头节点到了707设计链表时这个技巧能帮你省掉一大半头节点特判203里你熟悉了prev和cur的移动节奏到了206反转链表时这个节奏会演变成pre、cur、nxt三指针的接力。所以这三道题放同一天不是巧合而是刻意编排的递进训练。1.3 在纸上画链表比写代码更重要先告诉你一个我在实际刷题中最深刻的体会不要在键盘上直接写链表代码先在纸上画链表。把节点画成方框把next指针画成箭头然后拿着笔把箭头重新连一遍。这个方法听起来笨但极其有效。尤其是206反转链表很多人在代码里绕来绕去写不对但如果你在纸上画出1→2→3→4然后用橡皮把箭头改成4→3→2→1你会发现整个过程就是“逐个把箭头掉头”而已代码只是把这个过程翻译成了循环。我甚至建议你写任何链表题之前都先画三步第一步画原始链表第二步画出你想得到的目标状态第三步思考“每一步指针操作之后哪个节点的信息会丢失需要提前保存”。把这个习惯练成肌肉记忆链表题基本就稳了。2. 203题移除链表元素的思路拆解与实现要点2.1 先想清楚“删除节点”到底在做什么203题的题目很直白给定一个链表头节点head和一个整数val删除链表中所有值等于val的节点返回新的头节点。很多人一上来就写“如果当前节点值等于val就把当前节点删掉”然后用一个cur指针从头遍历。但这里有个隐蔽的问题单链表只能从前往后走你是无法知道“上一个节点是谁”的而没有上一个节点你就没法完成删除操作。删除的本质是把前一个节点的next指向被删节点的next。也就是说真正的操作对象是“被删节点的前驱”而不是被删节点本身。这就是为什么这道题最简单的写法要维护一个prev指针让prev始终指向当前遍历节点的前一个位置检查prev-next是否需要删除。如果你只用cur指针硬写会遇到一个很麻烦的问题头节点怎么删头节点没有前驱你必须单独写一段逻辑去更新head本身。这当然能做但代码会变得支离破碎而且很容易在边界处出错。2.2 虚拟头节点让头节点的处理不再特判解决头节点特判问题的标准做法就是引入虚拟头节点也叫dummy node。具体做法是new一个值为0的节点让它的next指向head然后从dummy开始遍历。这样一来原来的头节点也有了前驱删除逻辑就完全统一了不管删的是不是头节点都走“prev-next prev-next-next”这一条路。为什么最后要返回dummy-next而不是head因为head可能已经被删掉了你无法确定它还是不是链表的头。而dummy节点永远存在dummy-next才一定是当前链表真正的头节点。这是一个极其常用的技巧后面203、19、82题都会用到甚至双向链表、LRU缓存设计里也有它的变体。注意C里使用new创建的dummy节点函数结束前记得delete掉避免内存泄漏。刷题平台一般不查这个但面试官偶尔会追问。2.3 完整实现与复杂度分析先看C版本的完整实现ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0, head); // 虚拟头节点next指向head ListNode* prev dummy; while (prev-next ! nullptr) { if (prev-next-val val) { ListNode* tmp prev-next; // 先保存待删节点 prev-next prev-next-next; // 跳过待删节点 delete tmp; // 释放内存 // 注意这里prev不移动 } else { prev prev-next; // 只有未删除时才移动prev } } ListNode* ans dummy-next; delete dummy; return ans; }这里有一个非常关键的细节当prev-next的值等于val并完成删除后prev一定不能移动。因为新的prev-next是原来被删节点的后继它的值可能也等于val需要继续检查。只有当前节点不需要删除时prev才向后移动。这个细节我第一次写的时候就踩了坑盯着屏幕看了半天循环为什么跳过了连续重复的val。再给一个Python版本Python没有指针理解起来更直观def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]: dummy ListNode(nexthead) prev dummy while prev.next: if prev.next.val val: prev.next prev.next.next else: prev prev.next return dummy.next时间复杂度O(n)每个节点最多访问一次空间复杂度O(1)只用到了常数级的额外指针。2.4 不用虚拟头节点的写法看差距在哪为了让你更直观地理解虚拟头节点节省了什么我贴一下不用的写法核心逻辑// 先单独处理头节点 while (head ! nullptr head-val val) { ListNode* tmp head; head head-next; delete tmp; } // 再处理后续节点 ListNode* cur head; while (cur ! nullptr cur-next ! nullptr) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } return head;你看代码量差不多但逻辑分了两个阶段头节点的处理要单独写一个while循环。如果哪天题目改成“删除所有值等于val的节点并返回新的头节点”这种写法的出错概率明显更高。虚拟头节点的价值不在于减少代码行数而在于让逻辑变得统一、不容易遗漏边界。这也是为什么所有主流题解都会推荐dummy节点。3. 707题设计链表一次吃透增删改查的所有边界3.1 你要实现的不是“功能”而是“指针纪律”707题要求你设计一个链表类实现get(int index)、addAtHead(int val)、addAtTail(int val)、addAtIndex(int index, int val)、deleteAtIndex(int index)这五个方法。这题在LeetCode上标着“中等”但其实没有任何高深的算法它就是把你对链表操作的理解拿出来逐项检查。我常说这题考的不是智商是纪律。什么叫纪律就是每次操作前先想清楚三个问题第一index是否合法第二我怎么走到目标位置第三改指针之后还有没有指针指着我下一步要访问的节点。任何一个问题没想清楚代码就会出现段错误、死循环或者逻辑错误。很多人在addAtIndex这里崩掉就是因为没想明白“在第index个节点之前插入”到底要从哪个节点出发走几步。我们先统一约定index从0开始第0个节点就是头节点addAtIndex(index, val)表示在第index个节点之前插入新节点。这一步理清了后面才有得聊。3.2 get与addAtIndex索引边界的核心判断get(index)的要求是如果index无效index 0或index size返回-1否则返回第index个节点的值。实现很简单从dummy-next出发走index步。这里最容易犯的错误是循环条件写成index 0还是index 0。记住因为头节点是第0个节点你要走到第index个节点就是从当前头节点开始走index步。比如get(0)应该站在原地就返回头节点的值。deleteAtIndex(index)的边界要更仔细index 0或index size时什么都不做。走到第index个节点的前驱然后跳过第index个节点。注意这里必须是从dummy出发走index步到达“前驱位置”很多同学从head出发结果删的永远是头节点的后继全乱套了。addAtIndex(index, val)是三种插入的统一入口。题目规定如果index size则插到链表尾部如果index size则什么都不做如果index 0则插到头部。你不用为这些情况写多个分支统一做法是从dummy出发走index步停在第index个节点的前驱位置然后插入新节点。提示707题要求自己管理节点C在deleteAtIndex时一定要delete删除的节点。如果不delete刷题平台内存不受影响但面试官很可能追问内存管理问题。3.3 加一个dummy哨兵节点代码会简洁得多设计链表的时候很多人会纠结“要不要用dummy节点”。我的建议是一定要用。原因很简单有了dummy节点addAtHead就变成了“在dummy后面插入”addAtTail就是“从dummy出发走到末尾再插入”deleteAtIndex永远不用考虑“删除头节点时head本身要更新”的问题。你可能觉得头节点特判也没多麻烦但你想想addAtHead和deleteAtIndex(0)同时存在的情况如果不用dummyaddAtHead要更新head成员变量deleteAtIndex(0)也要更新head成员变量。这两处逻辑散落在不同方法里很容易改一处漏一处。有了dummy之后head指针本身不参与任何操作所有方法统一通过dummy操作逻辑一致性大幅提升。另外类内部一定要维护一个size成员变量。add操作后sizedelete操作后size--。这样get和deleteAtIndex的合法性判断只需要跟size比较不需要临时遍历链表统计长度时间复杂度从O(n)降到O(1)。很多人忽略这个细节每次get时都遍历一遍结果deleteAtIndex里又遍历了一遍整体效率差很多。3.4 完整实现与易错点梳理下面给出一个完整的C实现重点看addAtIndex的实现方式class MyLinkedList { private: struct ListNode { int val; ListNode* next; ListNode(int val) : val(val), next(nullptr) {} }; ListNode* dummy; int size; public: MyLinkedList() { dummy new ListNode(0); size 0; } int get(int index) { if (index 0 || index size) return -1; ListNode* cur dummy-next; while (index--) { cur cur-next; } return cur-val; } void addAtHead(int val) { ListNode* node new ListNode(val); node-next dummy-next; dummy-next node; size; } void addAtTail(int val) { ListNode* cur dummy; while (cur-next ! nullptr) { cur cur-next; } cur-next new ListNode(val); size; } void addAtIndex(int index, int val) { if (index 0 || index size) return; ListNode* cur dummy; while (index--) { cur cur-next; } ListNode* node new ListNode(val); node-next cur-next; cur-next node; size; } void deleteAtIndex(int index) { if (index 0 || index size) return; ListNode* cur dummy; while (index--) { cur cur-next; } ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; size--; } };几个容易出错的点我单独拎出来说。第一addAtIndex里循环是while(index--)从dummy开始走index步这样循环结束后cur正好是第index个节点的前驱——这个细节是整道题的核心我用一个具体例子验证假设链表是5-6-7size3在index1处插入4预期结果是5-4-6-7。从dummy出发走1步到5这个节点这时在5后面插入4结果就对了。第二deleteAtIndex删除后要根据删掉的节点位置判断是否需要移动cur。这里因为我们已经通过循环到达了目标位置的前驱删除后不需要再移动直接break结束即可。第三addAtIndex中当index等于size时从dummy出发走size步会走到原链表最后一个节点在它后面插入就是尾插天然满足条件。当index等于0时走0步就是dummy本身在其后面插入就是头插。这也验证了统一逻辑的好处——不需要写任何分支。我把五个操作的边界情况整理成了一个速查表刷题时对着看就不会懵操作index条件从哪个节点出发循环步数最终效果get0 ≤ index sizedummy-nextindex返回目标节点值addAtHead无条件dummy0在头节点前插入addAtTail无条件dummy遍历到末尾在末尾插入addAtIndex0 ≤ index ≤ sizedummyindex在第index个节点前插入deleteAtIndex0 ≤ index sizedummyindex删除第index个节点4. 206题反转链表的两种核心思路与多种写法4.1 迭代法三指针是怎么想出来的206题要求反转一个单链表。有的人觉得这题很难有的人觉得很简单差距就在于有没有理解三指针迭代法的“接力”逻辑。想象你手里拿着一串链条你要把它掉个头最自然的做法是一个环节一个环节地松挂钩、掉头、再挂上。代码里就是这个过程。初始时pre指向nullcur指向head。每轮循环做三件事先用nxt保存cur-next因为马上要改cur-next不保存就找不到了然后把cur-next指回pre最后pre和cur分别向后移动——pre移到cur的位置cur移到nxt的位置。当cur走到null时pre就是反转后链表的头节点。核心的“为什么要先保存nxt”这个问题是我觉得整道题最关键的一问。我们来看一个具体例子链表1-2-3cur在1pre是null。执行cur-next pre1-next变成了null链表从1这里断成两截后面的2-3彻底丢失。所以必须在修改cur-next之前先让nxt cur-next把2保存下来。这个“先保存后继再改指向”是所有链表重排操作的通用法则。4.2 递归法把问题交给更短的链表递归法理解起来稍微抽象一点但代码极其优雅。核心思路是假设链表是1-2-3-4如果你已经成功把2-3-4这部分反转成了4-3-2那么现在只需要让2-next指向1再让1-next指向null整个链表就反转完成了。写成代码就是ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }这里最绕的是head-next-next head这一句。它表达的是“让head的下一个节点的next反过来指向head”也就是让原本的2-next 1。很多视频和文章都会画图解释但我个人的经验是如果递归版你实在绕不清楚不要死磕迭代法完全够用且面试更稳妥。递归版的隐患也很明显链表很长时会栈溢出。还有一种头插法值得一提。它创建一个新的dummy节点遍历原链表每取一个节点就插入到dummy后面。代码稍微多一点但思路非常直观把原链表的节点一个一个摘下来头插到新链表里最后新链表的节点顺序自然就反了。4.3 复杂度对比为什么反转链表常考反转链表的三种写法时间上都是O(n)因为每个节点都要处理一次。空间上有区别迭代法是O(1)只用pre、cur、nxt三个指针递归法要O(n)的栈空间链表长时可能爆栈头插法也是O(1)但需要额外创建一个dummy节点。面试官爱考这题是因为它可以在很短的时间内考察出一个人对指针操作的掌握程度。而且反转链表是所有链表进阶题的地基比如“反转链表的第m到n个节点”、“K个一组翻转链表”、“判断回文链表”全部以它为基础。如果你能闭着眼睛写出迭代版并流畅解释每一行代码说明链表基本功已经过关了。4.4 完整实现与变体延伸迭代版完整代码ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 第一步保存后继 cur-next pre; // 第二步反转指向 pre cur; // 第三步pre前移 cur nxt; // 第四步cur前移 } return pre; }头插法版本ListNode* reverseList(ListNode* head) { ListNode* dummy new ListNode(0); ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 保存后继 cur-next dummy-next; // 头插 dummy-next cur; cur nxt; } ListNode* ans dummy-next; delete dummy; return ans; }Python迭代版def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: pre, cur None, head while cur: nxt cur.next cur.next pre pre cur cur nxt return pre要验证代码的正确性拿1-2-3手动跑一遍初始prenullcur1。第一轮nxt21-nextnullpre1cur2。第二轮nxt32-next1pre2cur3。第三轮nxtnull3-next2pre3curnull。循环结束返回pre也就是3链表变成了3-2-1完美。5. 刷题中的常见问题与调试技巧实录5.1 最容易踩的五个坑我把这三道题做题过程中最容易踩的坑整理成一个表格每条背后都是我自己或身边朋友真实出过的bug坑出现场景原因解决方案未保存后继直接改next206反转、707插入改掉cur-next后原链表后半段丢失改next前先nxt cur-next删除后prev不移动203删除连续重复节点只删了一个新的节点还是目标值删除时prev原地不动继续检查从head出发而非dummy出发707的addAtIndex/deleteAtIndex走了size步或index步后位置偏移统一从dummy出发走index步index边界判断错误707的get/addAtIndex没有理清0 ≤ index ≤ size的差异对照上文的边界速查表检查递归反转导致栈溢出206递归版处理超长链表递归深度等于链表长度改用迭代法O(1)空间5.2 常用调试手段画图、打印、小规模测试链表题出bug后靠眼睛在代码里找通常效率很低因为问题往往发生在“指针状态的某一个中间时刻”。我的调试流程分三步。第一步把链表画在纸上用小方框代表节点用箭头代表next然后手动执行一遍代码看每一步箭头的变化是否符合预期。这个过程相当于在用最朴素的方式模拟CPU。第二步写一个printList辅助函数在每个循环的关键位置打印当前链表状态。这个方法治标很实用尤其是707题你可以在addAtIndex和deleteAtIndex前后各打印一次立刻就能看出“指针是否走到了正确的位置”。我实际刷题时遇到超过三分钟还定位不出来的bug就会打印基本立刻破案。第三步准备一组边界测试用例空链表、只有一个节点的链表、删除头节点、删除连续重复值、在indexsize处插入、删除最后一个节点。把这些用例跑一遍所有边界问题基本都能暴露出来。我见过太多人只拿题目给的示例测一遍就提交结果$错在边界上很可惜。5.3 三道题联动Day3之后你该练什么把这三道题吃透之后你已经掌握了链表题最核心的三个能力用dummy统一头节点操作、用prev指针处理删除、用多指针完成重排。接下来建议趁热打铁练这些进阶题19题“删除链表的倒数第N个节点”是203的变体需要快慢指针和dummy配合24题“两两交换链表中的节点”是206的变体本质上是在局部做两次反转82题“删除排序链表中的重复元素II”是203的加强版不仅要删重复节点还要考虑删除后是否需要继续检查142题“环形链表II”则需要用到双指针技巧。我个人实际刷题中的体会是链表题不能贪多一天吃透三道经典题比泛泛刷十道效果强得多。这三道题做完如果你能在手边没有参考答案的情况下把三个题的核心解法各写一遍并能说出每一步为什么要这么做就说明你已经形成了自己的链表解题框架。后面再遇到链表题你大概率会条件反射式地先问自己一句dummy要不要加指针在改之前要不要先保存后继走多少步才能到达目标位置这三问一问一个准。最后分享一个我坚持了很久的小习惯每天睡前在纸上画一个1-2-3-4的链表然后默写一遍反转链表迭代版的五行核心逻辑。坚持一周之后后面再碰到复杂的链表题你会发现大脑里自动就有了一幅指针接力的动图写代码的手感完全不一样。
