企业官网建设流程全解析

每次面试或者帮同事review代码，只要碰到“删除结点”这个操作，我基本都能在几分钟内判断出对方的数据结构功底在哪个档位。原因很简单：这个操作看似基础，实际把指针/引用修改、边界条件、内存管理、递归和迭代的选择全揉在了一起，任何一环想不周全，写出来的代码都会在某个意想不到的地方悄悄崩掉。我一直觉得，删除结点就是链表题里的“照妖镜”。

今天想借这个机会，把“删除结点”这件事从头到尾拆一遍。重点会放在一个特别高频的变体上：给定一个头结点和一个值x，删除链表里所有值等于x的结点。同时也会延伸到单链表删除单个结点的经典写法，以及二叉搜索树里删除结点的三种情况。看完这篇文章，你不仅能写出能跑的代码，还能知道每一行代码到底在防什么坑。

1. 删除结点的核心思路：先理解“删的是什么”

很多人写不好删除操作，不是因为语法不熟，而是没想清楚一个最根本的问题：在链表、树这类“靠引用关系连接”的结构里，删除结点到底改变的是什么。

1.1 删掉的是“关系”，不是“盒子”

数组删除元素，是把后续元素整体往前搬，数据本身还在内存里，只是下标位置变了。链表完全不是这个逻辑。链表里的每个结点就是一个独立的内存块，结点与结点之间靠指针（或者Python里的引用）串起来。真正定义“我在这条链上”的，不是结点自己，而是前一个结点指向它的那条指针。

所以删除操作的本质是：让前一个结点跳过当前结点，直接指向后一个结点。至于当前结点这块内存怎么处理，那是语言层面的第二件事。这个认知特别重要，因为我见过太多新手在删除时死盯着当前结点本身，一会儿改它的next，一会儿改它的val，结果把整条链搞成一团乱麻。正确的思路永远是：找到“前驱”，修改“前驱的next”。

二叉树删除结点也是一个道理，只不过它稍微复杂一点：每个结点除了可能有前驱（父结点），还有左右孩子。删除一个树结点，不仅要处理父结点对它的引用，还要决定它的左右子树何去何从。但核心逻辑没有变：先找到目标，再修改引用关系，最后释放资源。

1.2 “删一个”和“删所有值等于x”的差异

先把两个容易混的需求分清楚：

删除单个结点，比如“删除链表中值等于目标值的第一个结点”。这个操作只要找到一个满足条件的就停手，不需要继续往后看。写法上常见于删除制定位置结点、删除指定值结点这类基础题。

删除所有值等于x的结点，也就是标题里那个热门变体。这个需求必须从头到尾遍历整条链表，把所有匹配的结点都去掉，一个都不能漏。它的难度比前一个高一些，原因在于：当你删掉一个结点之后，前驱指针的位置和下一个要检查的结点之间，关系会发生微妙变化。如果处理不好，要么漏删，要么空指针崩溃。

顺便把不同数据结构的删除复杂度列一下，方便大家在做方案选型的时候心里有数：

这张表的核心结论是：链表的删除成本本来应该是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.next，prev就跳到了第二个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。

1. 初始：dummy.next = 1，prev指向dummy。
2. prev.next是1，值不等于2，所以prev移动到1。
3. prev.next是第一个2，值等于2，删除，此时prev.next变成了第二个2。prev不动。
4. 再次判断prev.next，仍然是2，值等于2，删除，此时prev.next变成了3。prev不动。
5. prev.next是3，值不等于2，prev移动到3。
6. 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 边界条件遗漏：空链表、单结点、头尾结点

删除类题目最常翻车的就是边界条件。我列出几个必测用例，大家可以对照着自查：

写代码之前，先在纸上把这几个用例过一遍。尤其是连续重复结点，很多人笔试时都能写出来，但一跑测试用例就挂，就是因为这个没想清楚。

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 隔着时间再看这道题：复杂逻辑永远先画图

说句实话，我现在写链表删除代码时，已经不太会在一开始就考虑“能不能让遍历和删除同时进行”，而是先画出链表结构图，标清楚每个结点的引用关系，再落笔写代码。复杂逻辑先从图上推演一遍，能省掉很多试错成本。

最后分享一个小技巧：当你觉得删除逻辑特别绕的时候，把问题转换成“我要不要保留当前结点”可能更直观。你不需要每一步都去想“前驱怎么改”，你只需要去想“每个结点是保留还是删除，保留的结点之间的相对顺序是什么”。然后，用一个哨兵结点作为新链表的头部，按顺序把保留的结点串联起来。这种“拆了重建”的思路在写链表的删除、过滤类题目时特别好用，既能避免对原链表改动时出现断链和误删，也让代码更易读。等你把这种方法用熟了，再回头看你以前写的那些花式指针操作，会忍不住觉得“这都什么鬼”。

在我实际使用中，这招几乎就是万能钥匙：凡是“不满足条件的结点不要了”这种需求，走一遍“新建哨兵+筛选保留结点”的流程，代码很少出问题。反正笨办法想清楚了，再去做那些花哨的原地操作，心里就有底多了。