企业官网建设流程全解析

“删除结点”这四个字，几乎所有学数据结构的人都绕不过去。我见过太多人第一次在链表上写删除，逻辑背得滚瓜烂熟，“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 为 NULL，cur 指向 head；每次发现 cur 不是目标，就把 prev 移到 cur，cur 移到 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 还是 NULL，prev->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到Python

3.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 来取新 cur，Java 版本删除后直接 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, val=0, next=None): 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.next

Python 版还有一个特别适合展示的递归写法，代码极短，尤其能体现“链表本质是递归定义”这一数学结构：

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 node，Python 两者皆可。如果你的项目里链表结点结构不允许修改，或者不想额外申请结点，也可以用二级指针避掉哨兵的内存开销，但可读性差。我个人观点是，少省那一个结构体的内存，多留点代码上的安全，长期看绝对划算。

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 一份排查清单速查表

我把几年里踩过的坑整理成一个清单，代码写完后按这个过一遍，能拦住九成以上的低级错误：

别看这清单简单，我每次给团队新人讲链表题，最后都会让他们拿这个清单自查一次。很多人程序跑不过，不是不会写，而是总漏掉某一项。

回到最开始那句话，删除结点，改链是骨架，边界是灵魂。你把这个道理吃透，“删除所有值为 x 的结点”对你来说就不会再是一道需要背答案的题，而是一套随时能推出来的基本功。我个人在刷题和实际开发里已经反复验证过：凡是链表改成哨兵写法，调试时间都会肉眼可见地缩短；凡是保留“先绕过再释放”习惯的时候，内存问题基本不会找我麻烦。建议你把这三版代码都动手敲一遍，然后删掉再默写，默写到不出错，这道题才真正属于你。后续如果你想继续深入，还可以把今天说的哨兵思想带到双向链表、循环链表、以及带哑结点的树结构操作中，很多看上去花哨的解法，底子都是今天这几十行代码。