“删除结点”这四个字几乎所有学数据结构的人都绕不过去。我见过太多人第一次在链表上写删除逻辑背得滚瓜烂熟“pre-next cur-next”随口就来真到代码一跑要么头结点删不掉要么删着删着把链表搞断了要么直接内存报错。尤其是“删除所有值为 x 的结点”这种题LeetCode 上对应的是第 203 题笔试面试里反复出现很多人在单个删除上都能写对一改成“所有值”就懵了。这篇我一次讲透从单链表最经典的删除所有值为 x 的结点开始把原理、代码、边界、坑全部拆开再往后扩展到二叉树删除结点这种变式代码给到可以直接抄的程度适合正在学数据结构的学生也适合准备面试想快速过一遍链表操作的开发者。1. 题目拆解与整体设计思路1.1 “删除结点”到底在考什么先说结论删除结点的本质不是“删”而是“改链”。你要把一个结点从数据结构里摘掉真正做的操作是让它的前驱结点跳过它直接指向它的后继。至于这个被摘下来的结点在 C/C 里你还要负责释放内存在 Java/Python 里交给垃圾回收这一步才是很多人忽略的。很多教材上的链表删除前提都是“已经知道目标结点的前驱”然后三步走把前驱的 next 指向目标的下一个结点再释放目标结点完事。但实际做题时题目往往只给你链表的头结点和要删除的值 x并不直接告诉你要删哪个结点你得像遍历查找一样先找到符合条件的结点再把它摘下来。链表本身的随机访问能力很弱只能从头到尾一个个走所以删除过程天然分两半一半是遍历查找一半是摘链释放。“删除所有值为 x 的结点”比删除单个值难的唯一原因就是要处理多个目标结点同时存在的情况。当你删掉一个下一个可能紧接着又是 x。如果你用的是“找到就删删完继续从头走”的思路时间会变成 O(n²) 不说还特别容易在边界上出问题。正确做法是一遍遍历边走边删整个过程只关心一件事当前这个结点的值是不是 x是就摘掉不是就继续往前走。1.2 为什么“删除所有值为 x 的结点”是高频题这道题在求职面试里出现频率极高因为它一题考了好几个关键能力第一个是动手写链表基础操作的能力第二个是边界条件分析的能力第三个是代码里对空指针的警觉性。三道坎层层淘汰。第一道坎是头结点就是 x 的情况。很多人初次写循环都是从 head 开始判断一旦头结点命中整个链表的“起点”就变了返回的头指针如果还是原来的 head你这链表就丢了一段。第二道坎是连续两个结点都是 x 的情况。很多人用“cur 删完就往后走”的逻辑实际上删除后 cur 已经变成被删结点后面的新结点了如果这个新结点也是 x同一轮就得继续判断否则就会漏删。第三道坎是空链表和链表删空后的返回。所以这道题是典型的“看起来简单、写起来翻车”的题。正因为它能在极小代码量里暴露这么多问题面试官才爱考。刷明白这一题链表基础操作里八成以上的坑你都能提前踩到。1.3 先弄清结点的存储形态链表结点在内存里靠“指针”串起来每个结点除了存数据还存着下一个结点的地址。示意图上画出一个方块带个箭头我们看着简单但写代码时你要始终记住链表结点不是数组它在内存里是散落的唯一能找到它的线索就是前一个结点存的 next 指针。单链表里要删除第 k 个结点你必须先拿到第 k-1 个结点。因为每个结点只知道自己后面是谁不知道前面是谁。这就导致删除的“重心”其实是遍历时的“前驱维护”。你在遍历链表时不能只盯着当前结点还要用一个变量一直记录当前结点的前驱否则等到发现当前结点是 x 时你想让前驱跳过它却发现自己根本没有前驱的引用。这是整个删除话题里最重要的一个思想理解了它后面所有代码都是这个思想的表达而已。2. 单链表删除结点的核心原理与那些坑2.1 删除的本质让前驱绕过目标删除一个结点的核心操作文字上就一句prev-next cur-next。这句话的意思是让当前目标结点 cur 的前驱 prev不再指向 cur改为指向 cur 的下一个结点。这样在“走链”的时候系统就再也找不到 cur 了它就被逻辑删除了。但是注意这句话成立有个前提你手上得有 prev 和 cur 两个指针并且 cur 确实就是 prev 的下一个结点。怎么维护呢标准做法是让 prev 和 cur 同步往前走初始时 prev 为 NULLcur 指向 head每次发现 cur 不是目标就把 prev 移到 curcur 移到 cur-next如果 cur 是目标就让 prev-next cur-next然后 cur 也移动到 cur-next而 prev 原地不动。这里有个细节很多人第一次写会懵为什么删完以后 prev 不往后移我给你捋一下。删掉 cur 以后prev 后面的结点已经变成了原来的 cur-next这个名字叫 nextNode。下一轮循环要判断的正是 nextNode而它的前驱还是 prev。所以 prev 不能动只有 cur 移动到 nextNode。如果你在这里把 prev 也往后挪了pre 就会跑到被删结点后面去链表就出现“断裂感”更麻烦的是连续目标结点会漏删。2.2 头结点的经典难题与哨兵结点如果目标结点正好是头结点呢刚才说的逻辑里 prev 还是 NULLprev-next cur-next 就是空指针访问直接崩溃。所以必须特殊处理头结点。处理思路有两派。第一派是“分类讨论”先把头部所有值为 x 的结点都删掉直到新的 head 不是 x然后再去处理中间的结点。这种思路能写但代码会出现两段结构相似的循环丑且容易漏。第二派是“哨兵结点”也叫 dummy node、头哨兵、虚拟头结点。做法是在真正的头结点前面临时构造一个并不属于原始链表的结点让它的 next 指向原来的 head。然后从哨兵结点开始执行那一套“prev 和 cur 同步走”的逻辑。既然哨兵结点永远不可能被删那么任何结点包括原来的头结点在删除时都有前驱了代码里那种“万一删到第一结点怎么办”的判断就可以彻底消失。这里说个实际体验我刷链表题这几年凡是涉及“表头可能被改”的操作几乎无脑用哨兵。它带来的收益不是代码变快而是代码变安全。你不用反复问自己“head 会不会变”最后统一返回 dummy.next 就行这个写法在 Java、Python、C 里都极其通用。2.3 内存释放与指针悬空逻辑删除之后语言层面的事情才开始棘手。C/C 里你 new 出来的结点不会因为“没人引用”就自动消失。你要在自己的代码里显式释放这也就是 free(cur) 或 delete cur 这一步。顺序很关键一定是先让前驱跳过 cur再把 cur 释放。如果你先 free(cur)再访问 cur-next期望拿到下一个结点地址这种行为就是访问了已被释放的内存属于未定义行为程序可能不报错也可能随机崩溃特别玄学。有人以为不报错就没事这是大忌。释放之后还有指针悬空的问题。你 free 掉 cur 之后如果有人还拿着一个指针指向这块内存比如你代码里的 prev-next 如果还指向 cur那这个 prev-next 就成了悬空指针后面再用 prev-next 去访问就是经典的 use-after-free。所以正确的顺序绝对不可颠倒先绕过后释放。如果是 Java 或 Python则不需要手动释放但你会反过来遇到另一个问题被删结点的 next 还指着链表中其他结点虽然它已经不在链上但对象本身还被局部变量引用着垃圾回收可能不会被立刻触发于是出现“看似删了内存却迟迟不释放”的困惑。实际开发中我们通常还会把被删结点的 next 置空比如 cur.next null逼它彻底脱离。这道算法题里不这么做也能过但养成这个习惯对理解引用很有帮助。2.4 必须处理的边界情况链表为空head 是 NULL那循环压根进不去直接返回 NULL。很多解法天然兼容这种情况但你要能说清楚为什么不会崩。链表删光所有结点值都是 x删到最后链表为空返回的应该是 NULL。如果你用了哨兵那 return dummy.next刚好就是 NULL。头结点为目标且不止一个比如 1-1-2要删的是 1。如果不加处理删掉第一个 1 之后新的头结点还是一个 1继续删。这个过程必须连续进行直到头不再是 1。链表尾部为目标最后一个结点是 x删除时 cur-next 是 NULL前驱要指向 NULL这正好说明链表结束了不需要额外判断。但在释放内存时你要确认 cur 不是 NULL 才去释放别把 NULL 给 free 了虽然 free(NULL) 在大多数实现里是安全的但绝不推荐依赖这个。光说原理不够下面上三套完整代码。我按 C、Java、Python 三个语言各写一版“删除所有值为 x 的结点”代码都能直接跑。3. 三个主流实现从C到Java到Python3.1 C语言版本双指针与哨兵两种思路C 语言版本最能体现指针的原始面貌也最考验对内存的理解。先看用哨兵结点实现的版本我用一个在栈上分配的结构体当哨兵#include stdio.h #include stdlib.h typedef struct Node { int val; struct Node *next; } Node; Node* createNode(int val) { Node* p (Node*)malloc(sizeof(Node)); p-val val; p-next NULL; return p; } void printList(Node* head) { while (head ! NULL) { printf(%d - , head-val); head head-next; } printf(NULL\n); } Node* removeAllX(Node* head, int x) { Node sentinel; sentinel.next head; Node* prev sentinel; Node* cur head; while (cur ! NULL) { if (cur-val x) { prev-next cur-next; free(cur); } else { prev cur; } cur prev-next; } return sentinel.next; } void freeList(Node* head) { Node* tmp; while (head ! NULL) { tmp head; head head-next; free(tmp); } } int main() { Node* head createNode(1); head-next createNode(2); head-next-next createNode(2); head-next-next-next createNode(3); printf(原链表: ); printList(head); head removeAllX(head, 2); printf(删除 2 之后: ); printList(head); freeList(head); return 0; }注意一个细节我在 while 循环里把 cur 的移动统一写成了 cur prev-next。删除时prev 没动prev-next 已经指到了被删结点后面那个新结点所以 cur 自动指向新结点没删除时prev 刚刚移到 cur 的位置prev-next 就是原来 cur 的 next。这两条路径都能让循环正确前进代码结构上也更简洁。如果你想让代码更接近教材的“删除流程”也可以不用哨兵改成二级指针。二级指针的写法是很多老 C 程序员的偏爱它的思路是直接操作“指向头指针的那个指针”这样头指针本身可以被函数修改免掉哨兵。原理和哨兵是相通的。但二级指针可读性差点我建议初学者先掌握哨兵再看二级指针去理解“指针的指针”这种高级玩法。3.2 Java版本dummy node 让边界消失Java 里没有 malloc/free结点的生命周期完全靠引用管理代码表达上最干净。最常见的写法是 LeetCode 203 的标准答案class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } } class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; ListNode cur head; while (cur ! null) { if (cur.val val) { prev.next cur.next; } else { prev cur; } cur cur.next; } return dummy.next; } }这段代码里我做了个小处理删除分支里 prev 不动else 分支里 prev 才移动最后 cur 统一用 cur cur.next 前进。注意我这个写法和 C 版本的处理方式有一个细微差别C 版本删除后通过 prev-next 来取新 curJava 版本删除后直接 cur cur.next。原因很简单cur 结点还活着它的 next 仍然有效所以可以直接取而 C 里不能先 free 再访问 cur-next必须先保存或者像 C 版本那样通过 prev-next 获得新位置。这里特别提醒 Java/C# 等带垃圾回收的语言你再也不用关心“先绕过还是先释放”的坑因为根本没有显式释放。但你得关心“被删除结点是否还持有下一个结点的引用”如果链表很长你只删掉中间一个它仍然指向下一个结点垃圾回收就没法把它整个回收掉。实际工程里建议补一句 cur.next null这个操作虽然算法题里不写也能过但表达的是你对“引用”这件事的理解。3.3 Python版本迭代与递归Python 链表结点通常用__init__定义删除写法跟 Java 很像class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def remove_elements(head: ListNode, val: int) - ListNode: dummy ListNode(0) dummy.next head prev, cur dummy, head while cur: if cur.val val: prev.next cur.next else: prev cur cur cur.next return dummy.nextPython 版还有一个特别适合展示的递归写法代码极短尤其能体现“链表本质是递归定义”这一数学结构def remove_elements_recursive(head: ListNode, val: int) - ListNode: if head is None: return None head.next remove_elements_recursive(head.next, val) if head.val val: return head.next return head这个递归的思路每一层只处理一个结点。先递归地把“除去头之后的整条链”中所有值为 x 的结点删干净结果接到 head.next 上。然后判断 head 自己如果 head 也是 x就返回已经被删干净的后续链 head.next否则保留 head返回 head。理解这个递归关键是抓住“递归边界 每层干的事”。边界就是空链表返回 None每层干的事就是把后面处理好再接回来再判断当前头。递归的空间复杂度是 O(n)因为要压栈所以工程上不如迭代版。但面试时如果你能把这个递归写得又快又对是非常加分的它能证明你不是背代码而是真正理解了链表结构。3.4 复杂度分析与选型建议三套代码的时间和空间复杂度完全一致时间 O(n)空间 O(1)递归版除外。你只需要遍历一遍链表就能把所有值为 x 的结点删除平均情况下每个结点只访问一次这是单链表删除的理论下界。迭代版本之间的选型如果是面试建议按照语言习惯做。C 就用哨兵Java 就用 dummy nodePython 两者皆可。如果你的项目里链表结点结构不允许修改或者不想额外申请结点也可以用二级指针避掉哨兵的内存开销但可读性差。我个人观点是少省那一个结构体的内存多留点代码上的安全长期看绝对划算。4. 变式扩展从单链表到更复杂的结构4.1 不知道前驱的情况下怎么删结点面试里有个经典变种只给你链表中的某一个结点指针要求你删除它但没给你头结点。单链表本身没法往前找前驱怎么办做法是“狸猫换太子”把目标结点的下一个结点的值拷贝到目标结点然后让目标结点指向下下个结点再删掉下一个结点。代码在 C 里长这样void deleteNode(Node* node) { Node* nxt node-next; node-val nxt-val; node-next nxt-next; free(nxt); }限制条件是这个结点不能是尾结点因为没有下一个结点可以顶替它。这个技巧在 LeetCode 上对应第 237 题代码只要三行但背后的思想是“我们以为删的是 A实际删的是 B把 B 的灵魂值留在了 A 体内”。这种思路在数据规模小的时候没问题但如果结点里存储的是体积巨大的数据或者其他结构体拷贝的开销就上来了。面试正好可以借这个话题展示你对空间、时间复杂度的权衡能力。4.2 双向链表与循环链表的删除双向链表删除相对简单因为每个结点既有前驱指针又有后继指针天然知道自己前面是谁。删除时要做的是让前驱的 next 跳过自己让后继的 prev 跳过自己然后释放void deleteNodeDLL(Node* target) { if (target-prev ! NULL) { target-prev-next target-next; } if (target-next ! NULL) { target-next-prev target-prev; } free(target); }注意两个 if 都要判断尤其删除的是头或尾时其中一个方向的指针是 NULL不做判断就是空指针访问。循环链表稍微特殊点它没有 NULL 结尾判断结束条件不能再是 cur NULL而是 cur 重新绕回 head。具体实现时你先确定一个起点用 do-while 至少走一次走到起点说明遍历完整一整圈。很多新手第一次写循环链表把 while 写成了进不去或者死循环还是要回到底层认知上结束条件必须跟起点挂钩而不是跟 NULL 挂钩。4.3 二叉搜索树中删除结点从链表跳到二叉树删除的难度一下子增加了因为二叉树的结点一般有两个孩子删一个结点还要保证剩下部分仍是一棵合法的树。如果是二叉搜索树BST删除时按孩子数量分三种情况没有孩子直接删父结点对应指针置 NULL。只有一个孩子让父结点的指针指向这个唯一孩子相当于“隔代顶替”。两个孩子不能简单顶替得找“后继结点”或“前驱结点”的值来替换当前结点然后把那个后继/前驱从原来的位置上删掉。这里有个比较完整的 Java 实现用的是找右子树最小结点作为后继的方式public TreeNode deleteNode(TreeNode root, int key) { if (root null) { return null; } if (key root.val) { root.left deleteNode(root.left, key); } else if (key root.val) { root.right deleteNode(root.right, key); } else { if (root.left null) { return root.right; } if (root.right null) { return root.left; } TreeNode successor root.right; while (successor.left ! null) { successor successor.left; } root.val successor.val; root.right deleteNode(root.right, successor.val); } return root; }两个孩子的处理是整段代码最微妙的地方你先找到右子树里最小的结点 successor把它的值拷贝到 root 上然后递归去右子树里删除那个 successor 结点。这样表面看只改了值实际等于把“删除 root”拆成了两步既保持了二叉搜索树的大小顺序又绕开了“两个孩子的结点怎么调整子树”的难题。这个模式和我上面说到的“狸猫换太子”思路一脉相承只是这次拷贝值的代价远比调整整棵子树代价低。4.4 二叉树删除所有值为 x 的结点二叉搜索树只说删一个值。如果题目改成“删除二叉树中所有值为 x 的结点”就要先定好语义普通二叉树不像 BST 有顺序约束所以如果某个值为 x 的结点被删了它的整棵子树通常也一并丢掉否则剩余结点会变成“孤儿”。这种问题非常适合用后序遍历来写先递归处理左子树再递归处理右子树最后处理当前根结点。如果当前根的值等于 x就返回 null否则把它接好的左右子树组合后返回public TreeNode removeAllX(TreeNode root, int x) { if (root null) { return null; } root.left removeAllX(root.left, x); root.right removeAllX(root.right, x); if (root.val x) { return null; } return root; }你可能会问如果根结点是 x左右子树里还有 x我明明已经先递归删掉了左右子树里的 x现在直接返回 null那左右子树里那些不是 x 的结点不也全丢了吗对这正是“子树一并丢弃”的语义。如果出题人希望删除值为 x 的结点但保留其子树里的非 x 结点那是另一道复杂得多的树结构调整题需要把 x 结点的左右子树重新拼接到它父结点上。做任何树相关题目先和面试官确认清楚删除语义再动手这个习惯能帮你避开整段代码推倒重来的尴尬。5. 常见问题与bug排查实录5.1 头结点删不掉这是最高频的报错现象。测试链表第一个结点值就是 x跑完发现返回值还是原来的头结点等于没删。99% 的原因是你没有改返回值删除逻辑做对了但函数最后 return 还是 head而 head 根本没有被移动过。解决思路就是上一章说的要么用哨兵结点后统一返回 dummy.next要么在删除过程中用一个变量记录新的头结点并且头结点的更新必须发生在“删到第一个结点”的那一刻。5.2 删除后程序崩溃C/C 里最容易出这个问题。按你最初设想的思路先 free(cur)再让 prev-next cur-next逻辑上听着对但 cur 已经释放了你再取 cur-next 就是访问无效内存。程序可能当时没崩但你的堆结构已经被破坏了后续可能随机在某处崩一下特别难排查。正确顺序永远是先绕过、后释放二条顺序刻在脑子里。还有一种崩溃是空链表没判。你有 prev NULL然后循环里直接 prev-next cur-next空链表时 prev 还是 NULL。用哨兵结点就会自动免疫这个问题因为哨兵永远非空。5.3 连续的 x 被跳过链表是 1 - 2 - 2 - 3删值为 2结果返回 1 - 2 - 3中间那个 2 漏删了。问题出在删除操作之后cur 的移动逻辑错了。如果你删完一个结点就无条件 cur cur-next那么当被删结点的下一个结点也是 x 时这个 x 就被跳过了。正确逻辑是删完保持 prev 不动让 cur 移动到 prev-next 的位置由新 cur 继续判断。如果你用的是 Java 那种写法则要保证删除分支里 prev 不移动然后 cur cur-next 正好指向下一个待判断结点也能继续处理连续重复值。5.4 OJ 提交报错排查看这里在在线评测系统上写这道题除了逻辑错误还常见几类问题。第一内存泄漏。LeetCode 的判题机器虽然跑的是你的代码但如果你的 C 代码每跑一次就 malloc 一堆结点而不 free多次提交后可能触发内存超限或判题进程被影响。很多 C 题解故意不写 free这在算法比赛环境里勉强能过但工程习惯绝对不能容忍。第二返回值类型不对。有些题目要求你返回新的头结点有些要求你把删除后的链挂在原地址上还有些甚至要求不返回任何值只修改链表。写之前一定要看清方法签名这在 Java 里尤其重要别把 removeElements 写成了 void 返回结果回头函数还是被要求返回 ListNode直接编译不过。第三头结点的初始化。用 Java 写 dummy new ListNode(0) 时dummy 的值是多少其实无所谓因为永远不会被访问但你一定别让它指向 null 之后还去访问 dummy.next。写完代码多检查一遍这种方法签名和返回路径基本就能避开 OJ 的硬性报错。5.5 一份排查清单速查表我把几年里踩过的坑整理成一个清单代码写完后按这个过一遍能拦住九成以上的低级错误检查点说明空链表head 是否为 null/NULL函数是否能直接返回头结点为目标返回值是否为新的头结点而不是仍旧引用旧 head连续重复目标删除后 prev 是否没有移动新 cur 是否继续被检查删除顺序C/C 里是否先绕过、后释放是否访问了已释放内存尾结点删除prev-next 是否为 null链表是否正常结束内存释放是否每个 malloc/new 的结点都有对应 free/delete返回值路径每个分支是否都有 return哨兵写法是否返回 dummy.next递归遍历顺序树相关删除是否按正确的先序/后序处理子树别看这清单简单我每次给团队新人讲链表题最后都会让他们拿这个清单自查一次。很多人程序跑不过不是不会写而是总漏掉某一项。回到最开始那句话删除结点改链是骨架边界是灵魂。你把这个道理吃透“删除所有值为 x 的结点”对你来说就不会再是一道需要背答案的题而是一套随时能推出来的基本功。我个人在刷题和实际开发里已经反复验证过凡是链表改成哨兵写法调试时间都会肉眼可见地缩短凡是保留“先绕过再释放”习惯的时候内存问题基本不会找我麻烦。建议你把这三版代码都动手敲一遍然后删掉再默写默写到不出错这道题才真正属于你。后续如果你想继续深入还可以把今天说的哨兵思想带到双向链表、循环链表、以及带哑结点的树结构操作中很多看上去花哨的解法底子都是今天这几十行代码。