每次面试或者帮同事review代码只要碰到“删除结点”这个操作我基本都能在几分钟内判断出对方的数据结构功底在哪个档位。原因很简单这个操作看似基础实际把指针/引用修改、边界条件、内存管理、递归和迭代的选择全揉在了一起任何一环想不周全写出来的代码都会在某个意想不到的地方悄悄崩掉。我一直觉得删除结点就是链表题里的“照妖镜”。今天想借这个机会把“删除结点”这件事从头到尾拆一遍。重点会放在一个特别高频的变体上给定一个头结点和一个值x删除链表里所有值等于x的结点。同时也会延伸到单链表删除单个结点的经典写法以及二叉搜索树里删除结点的三种情况。看完这篇文章你不仅能写出能跑的代码还能知道每一行代码到底在防什么坑。1. 删除结点的核心思路先理解“删的是什么”很多人写不好删除操作不是因为语法不熟而是没想清楚一个最根本的问题在链表、树这类“靠引用关系连接”的结构里删除结点到底改变的是什么。1.1 删掉的是“关系”不是“盒子”数组删除元素是把后续元素整体往前搬数据本身还在内存里只是下标位置变了。链表完全不是这个逻辑。链表里的每个结点就是一个独立的内存块结点与结点之间靠指针或者Python里的引用串起来。真正定义“我在这条链上”的不是结点自己而是前一个结点指向它的那条指针。所以删除操作的本质是让前一个结点跳过当前结点直接指向后一个结点。至于当前结点这块内存怎么处理那是语言层面的第二件事。这个认知特别重要因为我见过太多新手在删除时死盯着当前结点本身一会儿改它的next一会儿改它的val结果把整条链搞成一团乱麻。正确的思路永远是找到“前驱”修改“前驱的next”。二叉树删除结点也是一个道理只不过它稍微复杂一点每个结点除了可能有前驱父结点还有左右孩子。删除一个树结点不仅要处理父结点对它的引用还要决定它的左右子树何去何从。但核心逻辑没有变先找到目标再修改引用关系最后释放资源。1.2 “删一个”和“删所有值等于x”的差异先把两个容易混的需求分清楚删除单个结点比如“删除链表中值等于目标值的第一个结点”。这个操作只要找到一个满足条件的就停手不需要继续往后看。写法上常见于删除制定位置结点、删除指定值结点这类基础题。删除所有值等于x的结点也就是标题里那个热门变体。这个需求必须从头到尾遍历整条链表把所有匹配的结点都去掉一个都不能漏。它的难度比前一个高一些原因在于当你删掉一个结点之后前驱指针的位置和下一个要检查的结点之间关系会发生微妙变化。如果处理不好要么漏删要么空指针崩溃。顺便把不同数据结构的删除复杂度列一下方便大家在做方案选型的时候心里有数数据结构删除逻辑核心最好情况平均/最坏情况额外注意点数组元素前移覆盖目标位置O(1)删末尾O(n)中间元素搬移长度变化索引容易混乱单链表修改前驱结点的next指针O(1)已知前驱O(n)需要先找到前驱头结点需要单独处理二叉搜索树三种情况叶子、单孩子、双孩子O(log n)平衡时O(n)退化链状时双孩子时要用“替身”策略这张表的核心结论是链表的删除成本本来应该是O(1)级别的但因为要找到前驱实际遍历的时间占了大部分。所以面试里经常会有“只给你待删除结点指针”的变种题就是为了考察你能不能绕过找前驱这一步。2. 单链表删除单个结点的完整实现先把最基础的单链表删除讲透这是后面所有变体的地基。假设链表定义如下本文所有代码都基于这个结构struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };2.1 基础版迭代写法前驱指针加哨兵结点如果要删除链表中第一个值等于x的结点最简单的思路是用一个指针从头开始遍历同时记住当前结点的前驱一旦找到目标就把前驱的next指向目标的next。ListNode* deleteFirst(ListNode* head, int x) { // 处理头结点就是要删的情况 if (head ! nullptr head-val x) { ListNode* toDelete head; head head-next; delete toDelete; return head; } ListNode* prev head; while (prev ! nullptr prev-next ! nullptr) { if (prev-next-val x) { ListNode* toDelete prev-next; prev-next toDelete-next; delete toDelete; break; // 只删第一个找到了就停 } prev prev-next; } return head; }这段代码里有两个细节值得单独说。第一个细节为什么循环条件是prev ! nullptr prev-next ! nullptr因为我们要通过prev访问它的next如果prev本身是空指针访问prev-next直接就崩了如果prev-next是空指针说明已经走到链表末尾没有可以删除的结点循环自然结束。第二个细节为什么删除之后用break跳出循环因为题目明确是“删除第一个”删完使命结束不需要再往后遍历。如果你把break漏了程序会继续用prev去访问后面已经变化的结构大概率踩到空指针。这个版本的写法能处理所有边界情况吗其实有一个地方很别扭头结点需要单独判断一次。每次都要写一句“如果头结点就是要删的怎么办”代码看起来不优雅还容易漏。更好的方案是用哨兵结点这个我在下一章讲删除所有值为x的时候会重点展开这里先不抢戏。2.2 递归写法用调用栈省掉显式前驱很多初学者不知道链表的删除也可以用递归写得非常干净。思路是不要总想着“我要找前驱”而是把问题拆成“当前结点和‘删除了后面所有值等于x的结点之后的链表’”。ListNode* deleteNodeRecursive(ListNode* head, int x) { if (head nullptr) return nullptr; head-next deleteNodeRecursive(head-next, x); if (head-val x) { ListNode* toDelete head; ListNode* newHead head-next; delete toDelete; return newHead; } return head; }递归的核心逻辑就三行如果head为空返回空否则先递归处理后面的链表把返回的新链表接到head-next上然后检查head自身要不要删除。这个写法不需要任何指针跟踪逻辑非常清晰。但递归有两个隐性成本。一是函数调用栈链表长度如果达到几万、几十万级别递归可能直接栈溢出实际工程里要慎用。二是内存释放容易出问题。如果用的是C删除结点之后必须释放内存但上面的代码里如果直接用head head-next然后return原结点的内存就泄漏了。所以我刻意写了toDelete这个临时变量先把要删的结点记下来改完引用关系再delete。这一步千万别省。使用Java、Python这类带垃圾回收的语言时不需要手动释放内存递归写法看起来会简洁很多比如Python版可以写成def delete_node_recursive(head: ListNode, x: int) - ListNode: if head is None: return None head.next delete_node_recursive(head.next, x) if head.val x: return head.next return head这个版本递归回溯的时候会从尾部开始逐个判断要不要删。因为回溯的过程中如果发现自己等于x就直接返回中间的next上一层的head.next就会指向这个返回值跳过当前结点。逻辑很精妙但对新手来说不如迭代直观。2.3 特殊变种只给待删除结点指针怎么办这是一道很有意思的面试变体给你一个单链表的非尾结点指针要求把它删掉但是不给你头结点也不给你前驱结点。常见的链表模型里没有前驱根本没法改引用怎么删技巧是用“值覆盖”来代替“改指针”。既然我们拿不到前驱那就把当前结点的值改成下一个结点的值然后删掉下一个结点。这样就相当于把当前结点“变成了”下一个结点而下一个结点本来就要被干掉链路依然完整。void deleteNodeWithoutHead(ListNode* node) { // node一定不是尾结点这是题目的前提 ListNode* next node-next; node-val next-val; node-next next-next; delete next; }这个写法的最大限制就是node不能是尾结点。如果node是最后一个结点node-next为空程序直接空指针崩溃。所以面试里出这道题时题目通常都会明确标注“node不是尾结点”但很多人写代码时还是会忽略这一点。我分享一个实际遇到的场景。有一次我在做内存池的回收逻辑简化模型就是这种单链表结点复用。当时我需要移除一个已知地址的空闲块但因为内存池的实现里每个block并没有反向索引到前驱所以只能采用“把下一个block的内容拷贝过来再删掉下一个block”的方式。当时踩了个坑如果我传入的是尾结点next为空调用delete next直接崩。后来在接口入口处加了这个断言问题才彻底解决。3. 删除所有值为x的结点变体拆解与实操这个变体是最常见的链表删除题之一也是本篇文章的绝对重点。需求一句话给定头结点head和一个整数x删除链表中所有值等于x的结点返回新的头结点。3.1 核心难点遍历时“前驱指针到底动不动”我重点讲一个特别容易错的地方可以说是这道题的分水岭。很多人在写迭代解法时逻辑是遍历链表遇见值等于x的结点就删然后无条件把当前指针往后挪一位。写成伪代码是这样prev dummy while prev.next ! null: if prev.next.val x: prev.next prev.next.next prev prev.next # 错误这里不管删没删都移动了问题在哪里考虑链表1 - 2 - 2 - 3删除所有值为2的结点。当prev指向1的时候发现prev.next第一个2等于2于是把prev.next指向第二个2。正常情况下下一步应该重新检查新的prev.next也就是第二个2是不是也要删除。但如果代码里无条件写了prev prev.nextprev就跳到了第二个2那么第二个2永远不会被检查直接漏删。正确的做法是只有当当前结点不能删除时prev才往后移动一旦发生了删除操作prev保持不动因为prev.next已经被更新成了新的后续结点需要重新检查它。ListNode* removeElements(ListNode* head, int x) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (prev-next ! nullptr) { if (prev-next-val x) { ListNode* toDelete prev-next; prev-next toDelete-next; delete toDelete; } else { prev prev-next; } } return dummy.next; }用实际的链表走一遍1 - 2 - 2 - 3删除2。初始dummy.next 1prev指向dummy。prev.next是1值不等于2所以prev移动到1。prev.next是第一个2值等于2删除此时prev.next变成了第二个2。prev不动。再次判断prev.next仍然是2值等于2删除此时prev.next变成了3。prev不动。prev.next是3值不等于2prev移动到3。prev.next为空循环结束。看到没有正是因为删除时prev不动连续重复的值才不会漏掉。这个点理解了这道题基本就掌握了一大半。3.2 为什么用哨兵结点统一处理头结点上面的代码用了一个dummy结点也就是“哨兵结点”。它的作用不是存储有效数据而是让“头结点”从特殊位置变成普通位置从而免去“如果头结点也要删除怎么办”的判断。如果不用哨兵头结点的情况得多写一段ListNode* removeElementsNoDummy(ListNode* head, int x) { while (head ! nullptr head-val x) { ListNode* toDelete head; head head-next; delete toDelete; } if (head nullptr) return nullptr; ListNode* prev head; while (prev-next ! nullptr) { if (prev-next-val x) { ListNode* toDelete prev-next; prev-next toDelete-next; delete toDelete; } else { prev prev-next; } } return head; }对比两个版本哨兵结点版本代码更短逻辑更统一完全没有“头结点特判”。原因是无论head怎么变化我们最终都返回dummy.next这个dummy永远是链表的逻辑入口前面的删除操作可以一视同仁。这也是为什么我强烈建议在实际写删除类逻辑时优先考虑哨兵结点。有个细节要注意dummy结点是栈上的局部变量函数结束后自动销毁不会造成内存泄漏。但如果你在Java/Python里用new ListNode(-1)这种方式创建dummy注意别在返回时把dummy本身返回给调用方。3.3 从链表延伸到树删除所有值为x的结点同样的套路也可以扩展到树上。比如要求“删除二叉树中所有值为x的结点返回新的根结点”。这里我用递归的方式写因为树结构天然适合递归。TreeNode* removeAll(TreeNode* root, int x) { if (root nullptr) return nullptr; root-left removeAll(root-left, x); root-right removeAll(root-right, x); if (root-val x) { // 删除当前结点把左子树挂到右子树的最左下角 if (root-left nullptr) return root-right; if (root-right nullptr) return root-left; TreeNode* cur root-right; while (cur-left ! nullptr) cur cur-left; cur-left root-left; delete root; return root-right; } return root; }这个实现是“后序遍历”的思路先递归处理左右子树保证子树内部的删除都完成了再考虑当前结点。当前结点需要删除时为了不让左右子树丢失我把左子树整体挂到右子树的最左下端。这种合并方式适合不要求排序关系的普通二叉树。如果维护的是二叉搜索树合并方式要严格遵守大小顺序通常用“右子树最小结点”或者“左子树最大结点”来做替换逻辑会比这个复杂不少会在下一节详细讲。树这里要特别提醒C使用者如果一个结点有很多子结点删除当前结点后它的所有后代结点如果不再被任何结点引用就会变成“孤儿内存”。递归的方式在delete当前结点后其左右子树仍然在递归返回值中被保留所以不会泄漏。如果某个子树本身要全部丢弃记得先释放整棵子树再删除父结点。3.4 复杂度分析和适用场景小结删除所有值为x的结点无论用迭代还是递归时间上都必须完整遍历一次链表所以时间复杂度是O(n)。空间上迭代版本只需要几个指针变量是O(1)递归版本因为调用栈深度等于链表长度最坏空间是O(n)。对于可能非常长的链表工程上推荐迭代版。适用场景方面最常见的当然是算法练习和面试。实际开发中我在几种地方用到过类似逻辑消息队列的任务链表清理、缓存过期项的管理、空闲内存块回收。它们本质上都是“根据某个条件删除一批结点”只是条件从“值等于x”变成了“任务状态为已取消”“缓存过期时间小于当前时间”等等。把这一题的指针操作练熟迁移过去非常快。4. 删除结点最容易翻车的四个场景与排查实录这一章是我多年写代码和帮人review代码的教训总结。代码写对了只是一半还得知道它会在哪里挂、挂得好看不好看。4.1 内存问题C/C的delete、野指针与悬挂引用在C/C里写删除函数首当其冲的是内存问题。最常见的错误有两种。第一种是内存泄漏。只改了引用关系没有delete被删除的结点结点变成无法访问的堆内存长跑服务里几分钟就能吃掉大量内存。这个问题在写链表删除时几乎必犯一次而且很难通过常规测试发现——因为程序不会立刻崩溃只是内存悄悄上涨。第二是多次delete。同一个结点可能被两个指针指向比如删完某个结点之后你还留着一个已经失效的指针后面又delete了一次直接触发double free程序崩溃。预防方法很朴素删除结点之后不要再使用指向它的任何指针并且在Node写法里很容易出现这种情况如果没有把待删除结点单独赋给临时变量而是直接改指针回头想释放内存时发现指针已经指向别的地方了。我推荐一个固定套路凡是遇到要删除某个结点先用临时变量toDelete保存它然后改引用最后delete临时变量。这样既不会丢内存也不会在修改引用后找不到原始指针。Python/Java选手虽然没有手动释放内存的烦恼但也要注意别让老的引用继续留在某个列表或Map里否则垃圾回收无法回收它。4.2 边界条件遗漏空链表、单结点、头尾结点删除类题目最常翻车的就是边界条件。我列出几个必测用例大家可以对照着自查测试场景输入示例容易遗漏的问题空链表head nullptr一上来就访问head-next直接崩头结点就要删1 - 2删除1没处理头结点返回的还是旧head连续重复结点2 - 2 - 2删除2前驱指针错误移动导致漏删所有结点都要删2 - 2 - 2删除2删除后链表为空返回空指针删除尾结点1 - 2 - 3删除3while循环里没处理好删除后还得继续走全链路无匹配值1 - 2 - 3删除5遍历完整条链确保不会死循环写代码之前先在纸上把这几个用例过一遍。尤其是连续重复结点很多人笔试时都能写出来但一跑测试用例就挂就是因为这个没想清楚。4.3 死循环与断链问题死循环在链表删除里也很常见而且非常隐蔽。我见过的一种典型写法是在循环里手动把head head-next然后根据条件删除删除之后又继续head head-next导致跳过对某些结点的检查。如果链表里恰好没有满足删除条件的结点循环会一直走到末尾这还好如果删除条件恰好导致指针原地不动那么理论上可能出现无限循环因为某些结点永远无法被跨过。断链问题则是另一种典型错误修改指针时只改了被删除结点的前一个结点的next却没有把前一个结点接回给原来的head引用或者改的是一份副本而不是原链表。典型的错误代码是这样void deleteNode(ListNode* head, int x) { while (head ! nullptr head-val x) { head head-next; // 这种写法在函数内改了局部变量 } }如果调用方的head变量不是通过返回值或引用传递回去函数内部的head改动根本不会影响到调用方的链表。修改后必须通过“返回新头指针”或者“传入指向头指针的指针”才能生效。这是在C语言时代就存在的经典陷阱很多朋友在写C的时候也会踩到。4.4 调试技巧画图、打印、小用例推演链表调试和普通程序调试的体验不一样断点打在循环里你很难一眼看出整个链表长什么样。我的习惯是写一个无副作用的打印函数在删除前后分别打印整条链void printList(ListNode* head) { while (head ! nullptr) { std::cout head-val; if (head-next) std::cout - ; head head-next; } std::cout std::endl; }然后构造一个包含重复值的链表比如1 - 2 - 2 - 3 - 2 - nullptr删除2打印删除后的结果。如果输出不对用“手工画图打印前后对比”的方式很快就能定位问题。还有一个办法就是自测最小化样例。比如只测一个结点删除后返回nullptr、只测连续两个相同值、只测头结点和尾结点。这些最小样例能最快暴露出逻辑边界问题比直接拿几十个结点的随机链表测要好用得多。5. 实操心得与面试建议这一章不聊具体代码逻辑了聊一点我的个人经验和建议。毕竟这种题目面试和实际工程里出现的频率都很高同样的知识可以复用很多次。5.1 为什么“删除所有值为x的结点”是必练题我在带团队的时候新人入职前我会让他们先做两类题一类是反转链表另一类就是这道删除所有值为x的结点。反转链表考察的是对指针翻转的敏感度而删除所有值为x的结点考察的是“在遍历中同时修改结构”的能力。实际开发里删除、清理、批量移除这类操作无处不在尤其是基础组件和底层模块。这两个题练熟了很多动态修改数据结构的代码写起来会顺手很多。另外这道题的“变体能力”也特别强。换掉判断条件就能变成“删除链表中值介于[a,b]之间的结点”“删除倒数第N个结点”“删除重复结点保留一个版本”等等。把基础思路吃透遇到这些变形题至少知道从哪个方向下手比死记硬背十几道题答案的效率高得多。5.2 写删除代码时的一个小习惯把删除封装成helper如果一段代码里多处需要删除结点我建议写成一个helper函数。比如ListNode* deleteNextNode(ListNode* prev) { if (prev nullptr || prev-next nullptr) return nullptr; ListNode* toDelete prev-next; prev-next toDelete-next; delete toDelete; return prev-next; // 返回删除后的后继便于调用方继续判断 }这样好处很明显删除逻辑只写一遍所有边界情况都集中在helper里处理。主逻辑里只需要判断“当前next需不需要删”然后调用helper就行代码看起来非常干净也方便测试。实际工程里这种封装还能方便加日志、埋点、断言对排查线上问题帮助很大。5.3 隔着时间再看这道题复杂逻辑永远先画图说句实话我现在写链表删除代码时已经不太会在一开始就考虑“能不能让遍历和删除同时进行”而是先画出链表结构图标清楚每个结点的引用关系再落笔写代码。复杂逻辑先从图上推演一遍能省掉很多试错成本。最后分享一个小技巧当你觉得删除逻辑特别绕的时候把问题转换成“我要不要保留当前结点”可能更直观。你不需要每一步都去想“前驱怎么改”你只需要去想“每个结点是保留还是删除保留的结点之间的相对顺序是什么”。然后用一个哨兵结点作为新链表的头部按顺序把保留的结点串联起来。这种“拆了重建”的思路在写链表的删除、过滤类题目时特别好用既能避免对原链表改动时出现断链和误删也让代码更易读。等你把这种方法用熟了再回头看你以前写的那些花式指针操作会忍不住觉得“这都什么鬼”。在我实际使用中这招几乎就是万能钥匙凡是“不满足条件的结点不要了”这种需求走一遍“新建哨兵筛选保留结点”的流程代码很少出问题。反正笨办法想清楚了再去做那些花哨的原地操作心里就有底多了。