1. 题目拆解移除链表元素到底在考什么刷力扣的链表题很多人第一道做的是反转链表第二道就是203.移除链表元素。题目难度标着“简单”但坑一点都不少。题目本身一句话就能讲完给你单链表的头节点 head 和一个整数 val删除链表中所有值等于 val 的节点返回新的头节点。示例也很直观[1,2,6,3,4,5,6] 删掉 6得到 [1,2,3,4,5]。看起来人肉遍历一眼就能出答案但真上手写代码头节点删不删、连续重复值怎么处理、空链表怎么办这些细节一上来就容易把新手卡住。这篇文章我会用这道题作为切口把链表删除的底层逻辑、多种题解、边界条件和面试追问全部聊透顺便把我自己踩过的坑也一并列出来。1.1 题目原貌与隐藏考点先原样看一眼题目输入输出head [1,2,6,3,4,5,6]val 6期望输出 [1,2,3,4,5]head []期望输出 []head [7,7,7,7]val 7期望输出 []。这三个用例其实已经覆盖了大部分边界普通中间删除、空链表、全删光。这道题表面上只考察一件事——单链表的遍历和节点摘除。但真正隐藏的考点有三个头节点没有前驱节点删除它和删除中间节点的操作逻辑天然不同新手普遍会在这一步栽跟头。被删除的节点可能连续出现比如 [7,7,7] 删除 7如果只删了一个就往后走结果一定错。返回值必须是新的头节点而不是传入的 head——当 head 本身被删除时新头是谁这个问题没想清楚代码必挂。所以力扣把这个题排在链表入门位不是因为它简单而是因为它把链表操作最常见的几类坑一次性集中暴露。把这道题吃透后面再做删除排序链表重复元素、删除链表倒数第 N 个节点都会顺畅很多。1.2 链表删除和数组删除的本质差异要理解这道题的写法先得搞清楚一个问题链表删节点为什么比数组麻烦数组在内存里是一段连续空间删除某个元素后需要把后面所有元素整体前移时间复杂度是 O(n)但逻辑上很直白——用索引覆盖就行了。链表则完全不同每个节点在内存里是离散的靠一个 next 指针串起来。删除链表节点时不需要移动任何数据只需要把“前一个节点指向后一个节点”的指针重新接一下。用生活化的例子说链表就像一群人手拉手站成一排你想把其中一个人从队伍里撤走只要让他左边的人和右边的人重新拉上手中间那个人就出队了。这个过程不涉及其他人移动位置。但这里有个关键限制你只能顺着这只手拉手的方向从队首一路看过去。当你走到某个位置时你能看到的是“当前这个人”和“他身后的人”却看不到“他身后的人”后面还有谁——除非你通过 next 指针去取。这就是链表的访问特性随机访问是 O(n)只能从头遍历。删除一个节点时关键不是找到“要删的那个”而是找到“要删的那个的前一个”。因为只有前一个节点的 next 指针能被改写。这个认知直接决定了后面的所有解法。顺着这个思路很容易理解为什么头节点特殊它没有前一个节点你没法去改动“它前面的那个箭头”只能直接把 head 往后挪。2. 三种主流解法从朴素到优雅这道题的解法网上能搜到十几种但核心思想就三种直接遍历头节点单独处理、虚拟头节点统一操作、递归。我按推荐程度和思考层次分别拆一下每种都写清“为什么要这样写”。2.1 方案一独立处理头节点的直接遍历最容易想到的做法是分两步先用 while 循环把开头的、值等于 val 的节点全部删掉然后再处理中间节点。ListNode* removeElements(ListNode* head, int val) { while (head ! nullptr head-val val) { ListNode* tmp head; head head-next; delete tmp; } if (head nullptr) return nullptr; ListNode* cur head; while (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; }逻辑本身没问题但有一个明显的缺点头节点和中间节点的处理代码是两套写起来啰嗦而且很容易漏。我见过有人只写 if 不写 while结果 [7,7,1,7] 这种连续头节点用例直接挂掉也有人忘记在删除头节点后继续判断新的头节点是否是目标值导致残留。这种写法在面试时不是不能用但你需要额外解释清楚“为什么头节点要单独处理”并且把边界讲明白。作为刷题阶段的理解起点没问题但只掌握这一种后面遇到更复杂的链表题会很吃力。2.2 方案二虚拟头节点统一操作既然头节点的痛点在于“没有前驱”那就给它造一个前驱。这就是虚拟头节点dummy node的核心思路。ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } head dummy-next; delete dummy; return head; }关键地方只有两个cur 从 dummy 开始而不是从 head 开始这样 dummy 就是 head 的前驱头节点的删除逻辑和中间节点完全一致。当 cur-next-val val 时删掉 cur-next但 cur 不移动。这样如果下一个节点还是 val下一轮循环会继续在同一位置判断连续重复节点能被一次性清干净。这个方案最优雅的地方在于消除了所有“特例”。代码里只有一套 if-else 逻辑最容易出错的分支被直接抹掉了。我在实际刷题时只要是可能改动头节点的链表题第一反应就是建 dummy哪怕是反转链表、两两交换节点这类题dummy 都能让代码的边界处理清爽一大截。有人会问新建 dummy 节点会不会浪费空间其实就多了一个节点固定是常数级空间复杂度依然是 O(1)。为什么不直接在原链表上操作因为原链表头节点没有前驱强行省这一个节点代价是代码多出若干个 if 分支更容易出 bug得不偿失。新手阶段我强烈建议无脑用 dummy等熟练了再去想“能不能省”的问题。2.3 方案三递归解法与自相似性递归是这道题的另一条路代码非常短def removeElements(head, val): if head is None: return None head.next removeElements(head.next, val) if head.val val: return head.next return head核心思想是“对当前节点负责剩下的交给递归”。链表本身就是递归定义的结构一个节点加上一个更短的链表。递归函数先处理后续部分等回来之后再根据当前节点的值决定保留还是跳过。这个写法空间复杂度是 O(n)因为递归深度最多等于链表长度。面试时提递归可以展示对链表的理解但要注意如果链表特别长递归栈可能溢出所以它不是最优方案。我自己的建议是递归解法用来加深理解提交的时候还是用迭代法。三种方案放在一起看方案一是直观思维方案二是工程思维方案三是数学思维。都有价值但在面试场景里方案二最稳、最容易讲清楚。3. 多语言实作中那些绕不过去的细节力扣上这道题的提交语言五花八门C、Java、Python 是最主流的三种。很多人把代码从 C 翻译成 Python 时发现逻辑一样但就是报错或者反过来用 C 提交 Python 版的逻辑时出现内存问题。这里专门把语言差异讲清楚。3.1 C手动管理内存的正确姿势C 最大的特点是你要自己负责 delete。上面虚拟头节点代码里我写了 delete tmp也写了 delete dummy。这里有几个非常容易踩的坑删除节点时必须先保存待删除节点的指针再把 cur-next 重新指向最后 delete。如果不先保存把 cur-next cur-next-next 执行完你就再也拿不到原节点的地址了内存泄漏就发生了。delete 完之后绝对不能再去访问 tmp 的 next 字段因为这块内存已经被释放访问它就是读野指针。用 new 创建的 dummy 节点最后要 delete。但注意不要在 return 之后再 delete因为你要返回的就是 dummy-next如果你先删了 dummy 再返回没问题只要不删 dummy-next 就行。顺序反过来就会把结果链表头节点一起释放掉。有些题解图省事dummy 直接建在栈上ListNode dummy(0); ListNode* cur dummy;这样末尾就不用 delete dummy省一行代码。我个人更偏爱这种写法减少一个内存管理点。刷题阶段这样完全够用也少一次出错机会。3.2 Python/Java引用与 GC 视角下的陷阱Python 版本写起来极其简单class Solution: def removeElements(self, head: ListNode, val: int) - ListNode: dummy ListNode(0) dummy.next head cur dummy while cur.next: if cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.nextPython 里没有 delete 操作被摘除的节点没有引用指向它等垃圾回收机制自己处理。所以很多人觉得 Python 写链表“更安全”因为少了很多内存操作。但 Python 的坑在别处如果你在循环里写了 cur cur.next.next 而不是 cur.next cur.next.next意思就完全变了——前者只是把局部变量 cur 移到了下下个位置链表结构原封不动。新手经常在这里犯迷糊其实是把“指针变量”和“节点之间的链接”搞混了。Java 的情况类似都是引用类型GC 会回收没有引用的对象。但 Java 有一个更容易踩的点链表节点类写在内部时如果用的是非静态内部类会有隐式外部类引用不过力扣环境里通常没有问题。写的时候确认一下 ListNode 的结构定义就好。核心逻辑还是那句话修改链接用 node.next移动指针用 node node.next两件事必须区分清楚。3.3 时空复杂度O(n) 背后藏着什么这道题的时间复杂度是 O(n)空间复杂度迭代法 O(1)、递归法 O(n)。这些都是标准答案背就好。但我想补充两个容易被追问的细节第一个细节为什么迭代法空间复杂度是 O(1)因为不管链表多长你只用了固定几个指针变量dummy、cur、tmp加起来常数个。新建 dummy 节点虽然多了一个对象但数量不随 n 变化所以仍然是 O(1)。第二个细节删除节点本身的开销能否忽略在力扣环境里可以因为每个用例跑完进程就结束了不 delete 也不会造成严重后果。但在真实工程里如果链表节点数量很大频繁 delete 会产生内存碎片影响程序长期稳定性。所以在嵌入式开发里有人会设计“节点池”而不是频繁 new/delete。这就是为什么有些公司面试会追一句“如果你在写一个高并发服务这里会怎么做”。从这道题往深处挖能挖出不少系统设计相关的知识点。4. 边界条件与实战踩坑实录链表题有一个通性题解背得再熟边界一变形就容易挂。我自己早期刷题Fail 的记录里有相当一部分不是思路错而是边界没兜住。下面把最典型的坑整理成清单每个都对应一个实际报错场景。4.1 四类高危边界输入第一类空链表。head 为 nullptr / None直接返回即可。代码里写成 cur-next 判断时如果 cur 为 nullptr 就会空指针异常。所以循环条件一定要带 cur-next 判断确保 cur 本身有效。第二类所有节点都等于 val。比如 [7,7,7] 删 7正确结果是空链表。如果用虚拟头节点最后返回 dummy-next也就是 nullptr没问题。但如果在返回时不小心返回了 cur 或 head 而非 dummy-next就会把链表尾巴当成头返回。第三类头节点连续多个等于 val。记住要用 while 而不是 if。虚拟头节点方案因为删除后不移动 cur天然免疫这个问题这也再次说明为什么推荐 dummy。第四类尾节点等于 val。很多人写的循环是 while (cur cur-next)然后判断 cur-next 的值。问题在于当倒数第二个节点被删除后cur 指针还在原来的位置这时候它的 next 可能正好是那个值等于 val 的尾节点。但因为循环条件 cur-next 在下一轮还能进入所以其实能处理。真正容易翻车的是你在判断条件里用了 while (cur-next-next)跳过了对最后一个节点的检查。记住判断条件只关心 cur-next 是否存在不要太贪心去访问 cur-next-next。4.2 指针操作的两条铁律基于我自己多次 debug 的经验链表删除有两个铁律违背任何一条都会出问题。铁律一删除一个节点之前必须先持有它的前驱节点。这句话我已经在前面重复了多次但这里再强调一次链表的单向性决定了你无法从待删除节点倒推回前驱所以遍历时永远要留一个 prev 指针。dummy 方案无非是把“留前驱”这个动作提前做到位了。铁律二先改链接再释放节点。这个顺序不能反。有人图省事写 cur cur-next-next再去删原节点结果链接没接上链表就断了。正确的顺序应该像这样ListNode* toDelete cur-next; cur-next toDelete-next; delete toDelete; // 或者交给 GC顺序记不住的话就记一句话“先接新线再拆旧线”。就像电工换线一样你得先把新电线接好确认电流通了再去拆旧电线。如果先把旧线拆了新线又没接上整个电路就瘫了。4.3 本地调试与日志打印的小技巧力扣页面报错只给你输入输出不给你过程链表题一旦出错排查起来比数组题折磨得多。我的习惯是写一个 list 打印函数专门输出整条链表def print_list(head): res [] while head: res.append(head.val) head head.next print(res)然后把要测的用例手动构造出来一步步跑看每个循环之后链表变成什么样。比如 [1,2,6,3,4,5,6] 删除 6我在第两次删除操作后打印一下立刻就能看出是漏了中间节点还是尾节点没处理。还有一个更细的技巧自己构造“错题用例”。我通常固定用四个用例覆盖所有边界[] 空链表[7] 单个节点且要删除[7,7,7] 全部删除[6,6,1,6,6] 头尾都是目标值这几个用例如果能一次通过这道题基本就稳了。别嫌麻烦链表这种东西光靠脑子想很难想干净真跑一遍什么都清楚了。4.4 典型错误速查表我把最常见的报错整理成一张表提交代码前对着检查一遍能省不少时间错误现象根本原因修复方式输出开头还残留目标值头节点删除逻辑没处理或没循环处理使用虚拟头节点输出尾部还残留目标值循环把尾节点跳过了判断条件改为 cur-next 存在中间残留部分目标值删除后 cur 后移导致漏判删除后不移动 cur空指针异常循环条件没判断 cur 是否为 null加上 cur cur-next本地内存泄漏提示new 的节点漏 delete记录待删节点指针后 delete5. 一道题铺开的链表基本功清单刷题不能就题论题。203.移除链表元素看起来孤立实际上它和好几道经典链表题共用同一套底层操作。我在这里把相关的题型串一下同时给出一个通用模板后面遇到链表题可以直接套。5.1 删除类变体题一网打尽力扣里和“删除链表节点”沾边的题不少最典型的有删除排序链表中的重复元素83、删除排序链表中的重复元素 II82、删除链表的倒数第 N 个节点19。这三道题的核心和 203 高度重合83 题重复元素只保留一个其实就是“去掉相邻节点中值和当前相同的”同样是遍历加指针跳转。82 题所有重复节点都要删光难度提升但依然靠 prev 指针控制只是需要在发现重复时循环跳过整段。19 题删除倒数第 N 个节点常用双指针先走 K 步再同步移动找到目标前驱最后还是用 cur-next 跳过目标节点。这几道题放在一起刷你会发现它们都在反复训练同一件事找到目标节点的前驱然后接线。所以 203 虽然简单但它是整个链表删除体系的基石。我的建议是把 203 的迭代、递归、内存细节全部吃透再去做 82、19你会觉得思路非常顺。5.2 链表题的通用解题模板经过这几道题的锤炼我总结了一个三层模板覆盖面很广第一步判断是否需要虚拟头节点。凡是“头节点可能被删除/改变”的题直接用 dummy。这一点不用犹豫先建 dummy 不会错最多多一个节点开销。第二步确定前驱与游标。用一个 cur 指针从头或 dummy 开始走始终保证 cur 是“当前判断位置的前驱”。循环里判断条件优先写 cur-next 或 cur.next避免访问空指针。第三步操作节点。需要删除时先取到待删节点再执行类型于 cur-next cur-next-next 的操作需要插入或交换时先把新节点的 next 链好再接入前驱。用这套模板解 203 就是两步的事建 dummycur 从 dummy 开始循环判断 cur-next。解 19 也类似只是找前驱的方式变成了双指针。模板的价值不是让你背代码而是帮你把“每一步在干嘛”想清楚写代码时手不抖。5.3 面试官最常追问的三个问题这道题在面试里出现的频率不低因为难度适中适合展开考基础。我把自己被问过或围观别人被问过的问题整理一下附带回答思路面试官问一为什么不用数组存下所有值再去链表里删除回答思路数组方案需要 O(n) 额外空间且最终你必须重建链表结构本质上绕不开指针操作。更重要的是链表删除的核心价值就在于原地 O(1) 空间完成修改用数组等于把问题复杂化了。面试官问二如果链表有环这个解法还成立吗回答思路不成立。循环条件 cur-next 会一直非空从而死循环。所以严谨的解法是先做环检测确认无环才可以用。面试官抛出这个问题通常是想看你会不会主动想到鲁棒性。面试官问三把 val 换成“要删除多个不同值的集合”代码怎么改回答思路思路不变把相等判断换成集合成员判断即可例如 if (deleteSet.contains(cur.next.val))。复杂度依然是 O(n)。这个问题看起来是在考扩展实际上检验你有没有理解删除操作的本质。回答这类追问时最重要的是先说思路再说代码不要一上来就写。面试官要看的其实不是你能默写多少代码而是你对指针操作和边界条件的掌控力。从这道题往外扩展还有环形链表、反转链表、LRU 缓存等更复杂的结构等着去刷。但我个人刷了这么多链表题之后最深的一个体会是链表操作的核心能力不是“会做某道题”而是能在任意复杂场景下快速找到前驱、正确接线、安全释放。203 这道题把这些基本功浓缩到了一个最简单的场景里把它吃透后面刷题就是复制粘贴中的运用。
