“删除所有值为x的结点”——如果你刷过链表类题目对这个需求肯定不会陌生。它听起来平淡无奇很多人第一反应是“遍历一遍遇到就删”可真到白板上写代码或者上线跑测试时头节点的处理、连续重复值、递归栈溢出、内存释放这些细节会一个一个冒出来把原本以为的“送分题”变成“送命题”。我见过太多候选人在这个简单功能上翻车也见过线上代码因为漏删第一个节点导致数据错乱。这篇就把“删除节点”这个操作从头到尾拆开讲透考什么、怎么实现最稳、测试用例怎么设计、工程上还有什么讲究一步不落。1. “删除所有值为x的结点”到底在考什么1.1 题目定义与隐含条件先说清楚这个需求的完整定义给定一个单向链表的头指针 head 和一个目标值 x删除链表中所有节点值等于 x 的节点返回新的头节点。这里最容易被忽略的是“所有”两个字——不是删除第一个遇到的也不是删除某个指定位置的而是全部删除。比如链表是1 - 2 - 3 - 2 - 4x 2那结果必须是1 - 3 - 4两个值为 2 的节点都不能留。为什么拿这道题当考察点因为它虽然短小却覆盖了链表操作里最核心的几个基本功节点的遍历方式循环还是递归指针/引用的重新连接前驱节点的 next 要指向后继节点头节点的特殊性头节点没有前驱连续目标值的处理删了一个下一个可能还是目标值内存管理C/C 里谁负责释放节点。一句话总结这题不是考你能不能写出代码而是考你对链表结构本身的理解有多深。任何一环没想到代码跑起来就会出错。1.2 不看代码前先理解“删除”这件事的本质在动手写任何实现之前搞明白“删除节点”在链表里的物理含义非常重要。数组删除元素时我们要把后面所有元素往前搬链表不同每个节点在内存里是散落分布的节点之间靠 next 指针串起来。所谓“删除节点 A”本质上只做一件事把 A 的前驱节点prev的 next 指针从指向 A 改为指向 A 的后继节点next。至于 A 节点本身它仍然占据着内存只是不再属于这个链表了。所以 C 语言里通常还要跟着一个 free(A)而 Java / Python / Go 这些带垃圾回收或者有指针但不需要手动释放的语言只需要把引用断开等 GC 或运行时自己收拾残局。这个理解是后面所有代码的基础。很多人写删除函数时纠结“要不要把 node.next 置空”其实在单链表场景里只要前驱的 next 已经绕过它了这个节点就已经不可达置不置空都不影响正确性。置空只是防御性写法或者为了帮助 GC 早日回收。1.3 三个真正的难点基于上面的理解我再把“删除所有值为 x 的节点”里最容易出错的三个点单独拎出来讲难点一头节点可能是目标值。经典的错误写法是只用一个 cur 指针遍历遇到 cur.val x 就让 cur cur.next。初看没什么问题但它完全没考虑如果头节点就是 x那么链表的头指针应该更新为第二个节点。头指针一旦丢失整个链表就找不到了后面的遍历全是空谈。难点二连续多个节点都是目标值。比如链表是1 - 2 - 2 - 2 - 3x 2。删掉第一个 2 之后cur 应该指向哪里如果直接后移很容易跳过第二个 2如果原地不动又要保证不是死循环。这个位置的“要不要往前走一步”是新手最容易懵的地方。难点三删除节点的同时不能丢失后续链表。正确顺序是先保存目标节点的 next再让 prev.next 指向这个 next最后释放如果需要。如果反过来先把节点释放了再找 next就变成访问野指针直接崩溃。把这三个难点想透接下来的每种实现看起来都会很顺。2. 四种实现逐行拆解从最直觉写法到工业级写法2.1 双指针迭代法新手最该掌握的写法严格来说“双指针”在这个场景里是一个 prev 和一个 cur 指针前者负责记录当前遍历节点的前驱后者负责检查当前节点是不是目标值。public ListNode removeElements(ListNode head, int x) { // 先处理头节点连续等于 x 的情况 while (head ! null head.val x) { head head.next; } // 链表可能被删空 if (head null) { return null; } ListNode prev head; ListNode cur head.next; while (cur ! null) { if (cur.val x) { prev.next cur.next; } else { prev cur; } cur cur.next; } return head; }这段代码的逻辑顺序就是前面讲的三个难点的逐一解答先用一个 while 把头部连续的目标节点全部跳过这一步直接解决“头节点是目标值”的问题而且是连续多个都是的情况处理完头节点后prev 一定不是目标节点链表剩余部分就可以统一用“prev 做前驱”的方式处理遍历时只有 cur.val ! x 才移动 prev否则 prev 不动只改 prev.next。这样即使多个相邻节点都是 x也能全部删干净。这段代码应该背下来吗不建议背但建议把里面的“为什么这里用 while 而不是 if”“为什么 prev 只在不需要删除时移动”这两句话吃透。理解了这两句话以后任何链表删除类题目都能顺手写出来。2.2 哨兵节点法简化边界处理的“作弊器”双指针法固然不难但每次都要先想想“头节点可能要删”这件事确实烦。有没有办法让头节点和其他节点一视同仁有加一个哨兵节点dummy node。public ListNode removeElements(ListNode head, int x) { ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; ListNode cur head; while (cur ! null) { if (cur.val x) { prev.next cur.next; } else { prev cur; } cur cur.next; } return dummy.next; }哨兵节点的作用往本质上说就是给头节点人为制造一个“前驱”。这样原本复杂的头节点特殊处理就消失了删除逻辑对所有节点完全一致。这个写法我个人非常推荐理由有两个代码更短逻辑更统一不需要单独处理头部连续删除的循环返回时用 dummy.next天然规避了头指针丢失问题。代价是额外创建了一个节点对象。对于绝大多数场景一个节点的开销完全可以忽略不计。工程代码里这种为简化逻辑而引入的辅助节点非常常见不只是链表很多树、图中的虚拟根节点也都是同一个思路。2.3 递归写法代码最短但隐患也最隐蔽递归解法的思路是一个链表的“删除所有等于 x 的节点”可以这样理解——先删除除以头节点以外的剩余部分再回来判断头节点要不要删。def removeElements(head: ListNode, x: int) - ListNode: if head is None: return None head.next removeElements(head.next, x) return head.next if head.val x else head这段代码只有 5 行非常优雅也是很多“炫技型”面试官喜欢的答案。但我必须说清楚它的代价栈空间是 O(n)。链表有 10 万个节点递归就要压 10 万层栈Python / Java 默认栈深度根本扛不住直接 RecursionError 或 StackOverflowError它其实不是“原地”删除。每次递归返回新链表头某些语言里这更像是在“重建”链表和迭代法的原地修改语义不同新手看到head.next removeElements(head.next, x)这一步往往想不通为什么先递归处理后面再删除当前节点哪来的顺序依赖关于第 3 点展开说下这个代码的核心思想是“先假设头节点之后的链表已经处理完了恢复成一个没有值为 x 的节点的干净链表然后我只需要决定当前头节点去留”。递归之所以能从后往前处理是因为它需要等子问题先返回才能知道当前节点的 next 最终指向哪里。递归适合用来理解链表删除的递归本质也是很多高级数据结构操作比如树的删除、红黑树调整的基础所以不代表它没用但面试时我会先把迭代写法写出来再补充“还有一种递归写法”而不是一上来就递归避免让面试官觉得你只记得花哨方案、不考虑实际运行环境。2.4 原地删除 vs 新建链表工程选型的核心考量很多人在写这个功能时会犹豫我能不能直接新建一个链表把不等于 x 的节点穿起来答案是可以但要分情况。新建链表的做法遍历原链表val 不等于 x 时把节点追加到新链表尾部返回新链表的头。这种方式实现起来甚至更简单也不用管 prev 指针。但它有个致命问题新链表和原链表共享节点对象。拿 Java 来说你并没有真正“删除”原链表里的节点只是让新链表不再引用它们。原链表里的内存如果还有别的地方持有引用并没有释放。如果是 C/C 环境你还要额外考虑这些节点最终由谁 free处理不好就内存泄漏。什么时候适合新建链表面试中时间紧张只要求“逻辑正确”不深究内存语义输入数据量小节点对象生命周期短系统靠 GC 兜底输入是“不可变链表”或你不想修改原数据结构的场景。什么时候必须原地删除嵌入式/C 环境每个节点的内存都要手动管理链表本身被系统其他模块共享不能破坏其内部结构对性能有要求——新建链表通常还会引入额外的容器或者频繁的尾指针维护。我的建议默认写原地删除。因为它是最贴近“删除”语义的实线也最能体现你对链表结构的掌握。面试时如果面试官追问“还能怎么做”再补充新建链表的思路顺便聊一聊两种方式的差异能直接拉高印象分。3. 边界条件与测试用例这才是拉开差距的地方3.1 必须覆盖的六类基础用例光把实现代码写出来不算完能不能设计出有效的测试用例才是区分“会写代码”和“写对代码”的分水岭。针对“删除所有值为 x 的结点”我每次都会至少覆盖下面六类情况用例类型输入示例预期输出考察点空链表[], x1[]空指针防护单节点且为目标值[1], x1[]删空后 head 为 null单节点且非目标值[1], x2[1]不变头节点连续为目标值[1,1,1,2], x1[2]头部连续删除尾部节点为目标值[1,2,3], x3[1,2]尾节点删除全部节点为目标值[2,2,2], x2[]整条链删除这六类用例覆盖了所有位置头、中、尾、所有数量0 个、1 个、多个的组合边界。我实际做代码评审时也主要用这些用例来“试”候选人的函数。3.2 一个特别容易踩的用例头节点连环删除很多人在测试用例里只写了[1,2,3]删掉 1 这种情况忽略“连续两个头节点都是目标值”的场景。比如[1,1,2,3], x 1。如果你只在 while 循环外做了一次if (head.val x) head head.next;那删掉第一个 1 之后 head 指向第二个 1此时 head.val 仍然等于 x但已经没有再检查于是返回的就是[1,2,3]答案错误。这就是为什么前文 2.1 节的 Java 代码里单独写了一个 while 而不是 if。这个细节在 LeetCode 203 题里是经典陷阱在实际工程里同样会踩——比如清理链表中所有无效会话节点第一个节点无效第二个也可能无效。测试这条用例时还有个小技巧不要只断言最终结果还要在删除过程中打印链表的每个节点地址确认 prev 和 cur 的移动是否符合预期。有一些运行时错误比如死循环单纯看输出是看不出来的只能在过程日志里发现。4. 从面试题到工程实战删除语义设计、内存管理与进阶场景4.1 内存管理谁负责释放节点如果项目是 C/C实现“删除节点”时一定要回答一个问题free 的动作放在哪里很多人的第一反应是删除了当然立刻 free。但这里有个细节——如果链表节点包含在某个对象池、内存池或者共享资源里free 的时机就不是你说了算而是这个池子的管理者说了算。盲目的 free 可能造成其他持有该节点指针的模块访问野指针。一种更稳妥的设计是删除函数只负责“摘除”也就是prev-next cur-next;然后通过返回值或输出参数把被删节点的指针交还调用方由调用方决定是 free、复用还是标记为可回收// 删除所有值为 x 的节点返回被删除节点列表头 struct Node* remove_all(struct Node* head, int x) { struct Node dummy; dummy.next head; struct Node* prev dummy; struct Node* cur head; struct Node* removed_head NULL; struct Node* removed_tail NULL; while (cur) { if (cur-val x) { prev-next cur-next; // 把 cur 挂到已删除链表上 if (!removed_head) removed_head cur; else removed_tail-next cur; removed_tail cur; cur cur-next; removed_tail-next NULL; } else { prev cur; cur cur-next; } } // ... 调用方遍历 removed_head统一释放或复用 return dummy.next; }这种“摘除”和“回收”相分离的设计在操作系统内核链表、内存池实现里非常常见。面试如果写 C/C能聊到这一层会在“工程素养”维度有明显加分。4.2 从单链表到双向链表删除函数该怎么改单链表删除时需要拿到前驱节点所以要么双指针要么用哨兵节点双向链表每个节点都有 prev 指针所以删除逻辑会更直接public void removeNode(Node node) { if (node.prev ! null) { node.prev.next node.next; } else { head node.next; // 删除的是头节点更新头指针 } if (node.next ! null) { node.next.prev node.prev; } // 可选清理 node.prev null; node.next null; }但双向链表删除所有值为 x 的节点时反而多了一个容易错的地方删除当前节点后它的 next 节点的 prev 已经被改成 prev 节点此时游标指针要怎么移动我见过有人删完之后还把 cur 赋成 cur.prev 或者误用旧的 prev 指针结果程序直接错乱。我的经验是双向链表里同样可以借助哨兵节点dummy head / dummy tail让头尾操作统一这样删除游标节点后的指针移动变得非常规律——事实上Java 的 LinkedList 内部删除节点时用的就是类似的统一化处理思路。4.3 再进一步LRU 缓存中的删除逻辑链表删除不只在算法题里出现。实现 LRU 缓存Least Recently Used最近最少使用时核心数据结构是哈希表 双向链表而双向链表上每天高频执行的就是“删除指定节点”和“把节点移动到头部”这两个操作。这里的删除和我们前面讲的删除所有值为 x 的节点不一样但底层的“摘除节点重新连接前后指针”完全是一样的。区别只在于场景删除条件删除方式本题值等于 x遍历整条链LRU被命中过需要搬到头部已知节点位置O(1) 摘除LRU缓存满淘汰尾部最久未用删 tail.prev如果我相信自己已经吃透了“删除节点”的三个难点头节点处理、连续删除、指针重连那么 LRU 缓存里最麻烦的“移动节点到头部”就是“删除 头插”两件事的组合而已。我在工程实践里遇到过几次 LRU 实现错误查到最后都不是“怎么插入”的问题而是“删除时忘记更新 head/tail 指针”——尤其是双向链表只保护了 head、没保护 tail 时尾部删除会直接把 tail 指向一个已经不存在的节点。这再次验证了边界处理永远是链表操作的灵魂。写到这里把“删除所有值为 x 的结点”这个功能从题目定义、三种实现、边界用例到工程扩展都过了一遍。回头想想这类问题的价值不在于“能背出哪种写法”而在于每一次写出指针调整时心里都有清晰的图景谁的前驱、谁的后继、头指针要不要变、内存谁来回收。带着这几个问题去写代码代码自然就稳了。我个人在实际项目里最常用的还是哨兵节点法它让逻辑统一、不容易出边界 bug但面试讲述时反而会先讲双指针迭代法因为它更接近链表删除的原生语义也更能体现思考过程。希望这篇文章能帮你把“删除节点”从一道题目吃透成一个真正能用于生产的技能。
