单链表删除节点全攻略：虚拟头节点与递归思路详解

刷题这件事，大多数人都是从数组开始的，然后无一例外地栽在链表上。力扣第203题“移除链表元素”，是我这些年看下来最适合用来突破链表恐惧症的题目：它不涉及反转、排序那些花活，只考察一个最底层的问题——你会不会在一个单链表里删除一个节点。就这么个“简单”操作，能把虚拟头节点、双指针、递归返回值这些核心套路全串起来。这篇就围绕这道题，把思路拆开、把代码讲透、把坑填平，无论是刚入门刷题的新手，还是准备面试想快速过一遍链表基础的人，都能直接拿去参考。

1. 题面解读与核心难点

1.1 题目到底在考什么

题目本身一句话就能说清楚：给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val == val的节点，返回新的头节点。比如输入链表1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6，val = 6，输出应该是1 -> 2 -> 3 -> 4 -> 5。

说它简单，是因为解法就那两种：迭代和递归。说它经典，是因为“删除所有匹配节点”这句话背后藏着两个细节：第一，链表的删除操作本身需要找到待删节点的前驱；第二，头节点本身也可能被删掉，这时候整个链表的“入口”都变了，返回结果就必须跟着变。

很多新手在这一题上卡住，不是不知道p.next = p.next.next这种写法，而是从来没有认真想过一个问题：如果头节点就是待删除节点，那我们的“前驱”从哪里来？如果没有前驱，那头节点该怎么删？这就是整道题的核心难点，也是为什么虚拟头节点（dummy node）这个技巧在这道题里几乎是“规定动作”的原因。

1.2 删除操作的本质：先找到前驱

要想理解这题，先理解链表删除的物理结构。链表里的每个节点就像一个珠子，串在一根线上，每个珠子手里只攥着通向下一个珠子的那根线。现在要拿走一个珠子，只能让前一个珠子松手，改攥住后一个珠子的线。这里的关键点就出来了：你至少得知道前一个珠子在哪里。

但链表本身只给了你头节点，你在遍历的时候永远只能知道“当前节点”和“下一个节点”，没办法直接得知“上一个节点”。所以删除操作的实际执行，是在当前节点判断“下一个节点是不是我要删的”，如果是，就让当前节点跳过它。这意味着，遍历指针其实一直在扮演着“前驱”的角色。

这就解释了为什么很多第一次写这道题的人会写出这样的代码：遍历到cur.val == val的时候，让cur = cur.next试图“跳过”它。打印链表一看，没删掉。因为在单链表结构里，你让指针往后跳，只是让遍历视线挪开了，但前一个节点的next依然指着那个待删节点。真正要改的，是前一个节点的指针。

2. 迭代法实操：虚拟头节点一劳永逸

2.1 完整代码与逐行解析

我以C++版本为主讲，Python和Java版本放在后面对照，逻辑完全一致。先看C++整体代码：

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) {} }; class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* cur = dummy; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* del = cur->next; cur->next = cur->next->next; delete del; // OJ上不写也行，面试时最好清理 } else { cur = cur->next; } } return dummy->next; } };

逐行解释。第一件事是创建一个虚拟头节点dummy，它的next指向真正的head。cur指针也指向dummy。为什么要这样？因为我们需要一个工具人——一个总处在待删节点之前的节点。有了dummy，即使原来的head等于val，我们也能用cur->next访问到它，并且统一用“跳过”的方式删除它，不需要为头节点单独写分支。

主循环的条件是while (cur->next != nullptr)，注意这里不看cur自身，而是看cur的下一个节点。因为我们要判断的是“下一个节点是不是需要删除”。如果下一个节点是需要删除的，就执行cur->next = cur->next->next，把指向它的线直接接到它的下一个节点上，完成删除。这一轮cur不要往后移动，因为新的cur->next是刚刚接过来的节点，还需要再次检查它是不是也等于val，否则连续重复节点就漏删了。

如果下一个节点不需要删除，cur = cur->next，平移到下一个节点，继续检查它的下一个。循环结束后，所有值为val的节点都被跳过，返回dummy->next，也就是新的头节点。这里还有一个隐藏好处：即使原链表所有节点都被删光，dummy->next也会是nullptr，不会出现返回悬空指针的问题。

2.2 Python与Java版本对照

Python版本的代码结构完全一样，只是没有手动释放内存这一步（交给GC回收）：

class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: dummy = ListNode(0) dummy.next = head cur = dummy while cur.next: if cur.next.val == val: cur.next = cur.next.next else: cur = cur.next return dummy.next

Java版本也一样：

class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode cur = dummy; while (cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return dummy.next; } }

三种语言的要点就一句话：判断cur.next，而不是判断cur。这是迭代法唯一的灵魂。

2.3 时间复杂度与空间复杂度分析

时间复杂度是O(n)，因为每个节点最多被访问两次：一次是作为“下一个节点”被检查，如果没删，cur会移到它身上再作为“前驱”检查下一个。空间复杂度是O(1)，只用了一个虚拟头节点和两个指针，没有额外申请与链表长度相关的存储。复杂度这块没悬念，真正有悬念的是递归解法，它看起来简洁得令人怀疑人生，但空间开销实实在在。

3. 递归解法：思路简单但要注意返回值

3.1 递归的核心思想

递归的本质是“把一个大问题拆成同构的小问题”。对于链表来说，天然适合递归——每个节点都可以看作“当前节点 + 一条更短的链表”。题目说删除所有值为val的节点，那么对当前节点来说只有两种选择：如果当前节点等于val，就整个跳过它，只返回后半部分的处理结果；否则保留当前节点，并把它的next指向后半部分的处理结果。

用一句人话说：让函数自己处理“接下来的链表”，然后当前节点决定要不要跟在后半部分前面。写递归最重要的就是抓住“子问题是什么”，而不是在脑子里展开整个递归过程。

3.2 递归代码实现

class Solution { public: ListNode* removeElements(ListNode* head, int val) { if (head == nullptr) return nullptr; head->next = removeElements(head->next, val); return head->val == val ? head->next : head; } };

这段代码短得吓人，但每一行都有讲究。首先是边界条件：节点为空时返回nullptr，这是递归的出口。然后无条件先递归处理后面的链表，把结果接回head->next。最后看当前节点的值：如果等于val，说明当前节点也要被删掉，那就不返回它，直接返回已经处理好的后半段结果；如果不等于val，当前节点就还在，返回它。

用例子走一遍流程。链表是1 -> 2 -> 6 -> 3，val = 6。最深处先到3：3的next是空，返回nullptr后，3 != 6，返回3。上一层是6：6先接收了后半部分3（也就是6->next = 3），接着判断自己等不等于6，等于，所以直接返回3，放弃了自身。再上一层是2：接收了3接在2->next，判断2 != 6，返回2 -> 3。最上层是1：接收了2，返回1 -> 2 -> 3。完美。

3.3 递归的空间代价与注意事项

递归解法的代码简洁，但有一个不能忽视的成本：空间复杂度是O(n)。每次递归调用都会在系统栈上占用一份栈帧，链表的长度就是递归深度。对于长度几百的链表无所谓，但在嵌入式的内存受限场景，或者链表有几万几十万个节点时，可能直接栈溢出。刷题时能用迭代就用迭代，除非面试官明确要求写递归，或者题目本身就在练习递归。

还有一个常见误区：有人会把递归写成“先判断再递归”的形式，也就是在if (head->val == val)的时候返回removeElements(head->next, val)，否则递归处理后面。这在逻辑上没错，但代码会变成两个返回值路径，容易漏掉head->next的赋值，导致“删除后链表还是连着旧节点”的诡异问题。我记得踩过这个坑：写完发现输出结果里待删节点虽然不在返回链表中，但它的next还残留在某些路径上，打印循环直接死循环。所以递归写法推荐“先处理后判断”，一条返回路径走到底，不容易出幺蛾子。

4. 常见问题与本地调试实践

4.1 新手最容易翻车的三个场景

这道题别看简单，实际一跑就出错的情况我见得太多了。第一个是连续重复节点漏删。比如链表1 -> 6 -> 6 -> 3，val = 6。如果在删除节点后立刻把cur往后移动，第二个6就溜过去了。正确做法前面强调过：删除之后cur原地不动，继续验证新的cur->next。第二个是用while (cur != nullptr)作为循环条件，然后在循环里判断cur->val，结果发现删除最后一个节点后压根不知道前一个节点是谁，万般无奈又翻回头写pre双指针。虚拟头节点明明就是为了解决这个问题，没必要绕远路。第三个是忘记返回新头节点，最后返回了head。如果原头节点就是待删节点，这么做直接返回了一个已经在链上“悬空”的节点，输出结果完全不对。

4.2 常见错误对照速查表

4.3 本地可复用的调试工具函数

刷题进度的最大杀手其实是“本地一跑就编译报错，根本轮不到逻辑出错”。我的建议是平时就备好一套链表调试工具，不要每次都现写。比如C++里面，写一个从数组构建链表的函数和打印链表的函数：

ListNode* buildList(vector<int>& nums) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; for (int num : nums) { cur->next = new ListNode(num); cur = cur->next; } return dummy->next; } void printList(ListNode* head) { while (head != nullptr) { cout << head->val; if (head->next != nullptr) cout << " -> "; head = head->next; } cout << endl; }

有了这两个函数，配合测试用例[1,2,6,3,4,5,6]、[6]（单节点单删）、[]（空链表）、[6,6]（全部删除），直接本地验证逻辑，跑通了再贴回力扣提交。我喜欢在本地先把所有边界用例都跑一遍，再去OJ提交，省得反复试错。

5. 举一反三：从203到链表全家桶

5.1 同类型题目一网打尽

203题做会了，后面好几道题其实都是它的变体。力扣83题“删除排序链表中的重复元素”，是只保留一个重复元素，循环里改一个判断条件就行。力扣82题“删除排序链表中的重复元素II”更狠一点，重复元素全部删除，这就要先用前置指针判断“下一批是不是重复的”，本质还是前驱节点那一套。力扣19题“删除链表的倒数第N个结点”，需要用快慢指针先拉开距离，但删除时依然是寻找前驱节点的套路。力扣237题“删除链表中的节点”更特殊，它只给你待删节点本身，不给你头节点，巧妙做法是用下一节点的值覆盖当前节点再跳过下一节点——背地里玩的还是“前驱”概念。

这些题串起来看，你会发现链表删除题的核心就三条：找到前驱、改指针、处理头节点。虚拟头节点一上，三条路全通。做题时应该主动总结这个套路，而不是一题一题孤立地背代码。

5.2 刷题笔记如何记录才有价值

我一直建议刷题的人准备一份偏差笔记，记录的不是题解全文，而是“我当时为什么没想到”。比如203题，就记录“我试图直接用cur删除自己，但链表没有回头路，必须用前驱”。这种一句话复盘，比抄十遍代码都管用。具体做法：每道题做完，花两分钟在笔记里写三行——第一行是题号和题目一句话描述；第二行是核心套路（比如“虚拟头节点 + 前驱指针”）；第三行是我踩的坑或者恍然大悟的点。一个月后回头看，这份笔记才是真正的刷题资产。

还有个小习惯，就是讲题给别人听。找一个朋友或者干脆对着空房间，把这道题从头到尾讲一遍：为什么用虚拟头节点、循环条件为什么是cur->next、递归的返回路径是什么。你只要能把一个完全没准备的人讲明白，这道题就真吃透了。这个做法比再刷十道题都管用，尤其是在链表这种“自以为懂了但一动笔就卡壳”的知识点上。

5.3 迭代和递归到底怎么选

做203题时很多人会纠结：两种解法都会，该用哪种？我的建议是：默认迭代，笔试面试都优先给迭代解法，因为空间复杂度更低，而且虚拟头节点的思路可迁移性极强。递归解法可以当练习写一遍，体会“子问题”的分解方式，对后续二叉树的递归题有热身作用。但面试时如果主动写了递归，要有心理准备被追问“这个会不会栈溢出”——你能接住“深度为n时空间复杂度O(n)，而迭代是O(1)”这种回答，面试官反而会认可你对复杂度理解够深。

解题顺序上，先想清楚迭代怎么走，再试递归怎么写。反过来往往容易陷进递归的调用过程出不来，越画栈越懵。

最后分享一个实战小技巧。不管用什么语言，调试链表题时我都习惯把测试用例设计成五类：空链表、单个节点、头节点就是要删的那个、连续重复节点散落在中间、整条链全都要删。把这五类固定下来，每次做链表题先跑一遍这套用例，逻辑出错的概率能降一半。203题只是一个起点，但如果你能把这题的虚拟头节点和指针移动彻底想明白，后面遇到19题、82题、甚至复杂一点的链表反转题，都会明显感觉轻松不少。