1. 题目本身很简单为什么很多人还是写不对LeetCode 203 移除链表元素是一道看起来人畜无害的基础链表题。给定一个单链表的头节点head和一个整数val删除链表中所有节点值等于val的节点最后返回新的头节点。这道题的难度标注是“简单”但我和一些候选人模拟面试时发现越是这种题越能暴露基本功。有人把所有等于val的节点删掉之后返回的还是旧head直接导致结果错误有人在头节点就是待删节点时逻辑分支写成一团乱麻还有人面对连续多个相同值的节点删了一个就跳出循环漏删了后面的。为什么一道基础题会踩这么多坑核心原因有两个一是链表删除本身涉及指针/引用的重连和数组删除的思维完全不同二是头节点没有前驱节点是一个天然的特殊情况很多人处理不好这个特殊情况就开始堆if来打补丁补到最后代码又长又容易错。这篇文章我会把这道题拆开揉碎地讲覆盖哨兵节点、双指针、递归三种主流解法然后把容易出错的边界条件单独拎出来分析最后再聊聊和它相关的几道高频变体题。适合刚接触链表、准备面试算法部分或者想加深对链表指针操作理解的读者。2. 哨兵节点解法用哑节点把特殊情况变成普通情况2.1 核心思路为什么我们需要一个虚拟节点链表的删除操作本质上就是一句话让前一个节点的next指向当前节点的next。问题在于头节点没有前一个节点。如果你要删除头节点就得单独处理“新的头节点是谁”的问题。很多人的第一反应是写两个分支先循环删除头部等于val的节点再处理中间节点。这确实能跑通但代码里出现了一类叫做“特判”的东西。特判越多代码逻辑的分支就越多出错概率越高。更优雅的做法是造一个哨兵节点dummy node把它放在真实头节点的前面。这个节点本身不存储业务数据它的唯一作用就是作为头节点的“前驱”。这样一来原来的头节点就变成了一个普通节点删除它和删除其他任何节点没有任何区别。遍历结束后真正的新头节点就是dummy-next。2.2 完整实现代码class Solution { public: ListNode* removeElements(ListNode* head, int val) { // 哨兵节点next 指向当前链表的头 ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { // 删除 cur-next跳过该节点 ListNode* toDelete cur-next; cur-next cur-next-next; delete toDelete; // 实际工程中记得释放内存 } else { cur cur-next; } } ListNode* result dummy-next; delete dummy; return result; } };这段代码里最关键的地方是cur指针一开始指向dummy而不是head。整个循环过程中我们检查的都是cur-next的值。如果它等于val就删除它如果不等于就把cur向后移动一位。2.3 一个特别容易忽略的操作细节在循环内部删除节点之后cur并没有移动。这不是漏写而是有意为之。因为删除cur-next之后新的cur-next是原来那个节点的后继。这个后继节点的值也可能等于val所以需要继续检查。举个例子链表是1 - 1 - 1 - 2val 1。一开始cur指向dummy发现dummy-next的值是 1删除它。此时dummy-next指向第二个值为 1 的节点。如果这时候顺手让cur往后走就会跳过这个节点导致漏删。所以“删除后不移动当前指针”是这段代码的核心纪律。基于常见实践我再补充一点LeetCode 的在线评测环境不要求手动释放内存但在实际工程里被删除节点的内存必须释放否则就是内存泄漏。上面的代码我加了delete toDelete如果是 Java 环境不需要这一步只需让cur-next cur-next-next剩下的交给垃圾回收。3. 双指针解法不借助哨兵显式维护前驱节点有些面试官会追问如果我不想用 dummy 节点你还能写吗这时候双指针解法就派上用场了。3.1 双指针的视角让前驱和后继关系清晰可见不用哨兵节点就要自己维护两个指针pre指向前一个节点cur指向当前正在检查的节点。初始时cur headpre nullptr。当cur-val val时需要让pre-next直接指向cur-next否则让pre cur然后cur cur-next。这个解法对初学者更友好因为它把链表删除的“前驱-当前-后继”三层关系直接摆在明面上。缺点是需要单独处理头节点因为pre一开始是空的没办法执行pre-next cur-next。3.2 实现代码class Solution { public: ListNode* removeElements(ListNode* head, int val) { // 先处理头节点连续等于 val 的情况 while (head ! nullptr head-val val) { ListNode* toDelete head; head head-next; delete toDelete; } if (head nullptr) return nullptr; ListNode* pre head; ListNode* cur head-next; while (cur ! nullptr) { if (cur-val val) { pre-next cur-next; ListNode* toDelete cur; cur cur-next; delete toDelete; } else { pre cur; cur cur-next; } } return head; } };这段代码写出来后很多人会问为什么中间那段处理逻辑没有走到pre因为在进入循环之前已经用while把头部的所有目标节点都删掉了。此时head一定不是待删节点pre才能安全地初始化为head。3.3 双指针解法最常见的翻车点我见过不少人在这个版本上犯一个错删除cur之后直接把cur cur-next然后再执行pre cur之类的操作导致前驱关系错乱。正确做法是删除分支里pre不动只移动cur非删除分支里pre和cur一起向后移动。这里有个容易混淆的点。很多人的直觉是“既然是双指针两个指针就该同步移动”。但删除场景里pre在删除动作发生后不能移动因为它的next刚刚被重新指向了一个新节点。如果pre也往后走就相当于跳过了这个新节点下次就无法检查它。为了帮助记忆可以把两个指针的分工记成一句话pre永远指向当前链表中“最后一个确认不需要删除的节点”cur则负责向前探索。当cur遇到需要删除的节点pre的next跳过它当cur遇到安全节点pre就追上来和cur保持相邻。4. 递归解法把删除操作交给函数调用栈4.1 另一种看待链表的视角迭代解法站在“从前向后遍历”的角度递归解法换了一个视角链表可以看作“当前节点 一个更短的链表”。删除所有值为val的节点等价于先处理掉后面那个短链表中的所有目标节点再根据当前节点的值决定要不要把它也删掉。这个思路的代码特别短短到第一次看到的人往往不敢相信它能通过。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; } };三行核心逻辑加一个递归基。处理完后续链表后如果当前节点的值等于val就跳过当前节点返回它的后继如果不等于就保留当前节点返回它本身。4.2 递归的执行过程拆解以链表1 - 2 - 6 - 3 - 4 - 5 - 6val 6为例。函数一路调用下去直到最后一个节点的next为nullptr开始逐层返回。最底层返回nullptr给值为 6 的节点这个节点发现自己的值和val相等于是把它后面的结果直接返回给上一个节点相当于删除了它自己。上一层是值为 5 的节点它的next接下来指向nullptr因为节点 5 的值不等于 6所以返回自身。就这样一层层往回组装被删除的节点彻底从链表中消失了。有一点需要强调递归里的head-next赋值是必要的。因为下一层递归可能调整了后继节点我们必须把返回结果接回去。如果漏掉这一行链表后半部分的修改就传不回来整个递归失效。4.3 递归解法的代价和适用范围递归解法写起来确实是最清爽的但它有一个不能忽视的代价空间复杂度是 O(n)。每次递归调用都会占用一个栈帧链表长度为 n 时调用深度也是 n。对于特别长的链表递归很可能导致函数调用栈溢出。在实际工程里我一般只在链表很短、或者数据结构本身就是递归定义比如树时才用递归。生产环境的高频链表操作还是迭代加上哨兵节点更稳妥。但面试时把递归解法写出来能证明你对链表结构有更深层的理解尤其是能用一句话解释清楚“为什么递归天然适合链表”这个问题会很加分。5. 边界条件梳理空链表、连续重复值、全删除5.1 容易被测试用例打脸的特殊场景LeetCode 的判题系统覆盖的边界条件非常全稍不注意就会在某一个用例上翻车。我自己把边界条件分成四类按危险程度排序场景示例风险点空链表head null直接返回 null不要访问任何节点头节点就是目标值[1,1,1,2],val1需要连续删除多个头节点所有节点都是目标值[7,7,7],val7删除后链表为空目标值在链表末尾[1,2,3],val3删除最后一个节点后遍历正确结束先说空链表。无论哪种解法第一件事都应该是判断head是否为空。递归解法里这对应递归基双指针解法里对应前面那段while循环后的空指针判断哨兵解法里由于dummy永远存在天然不会因为空链表崩溃但返回dummy-next时仍然是空的符合预期。再说连续重复值。在迭代解法里删除节点后不能立即让当前指针前进这个我在哨兵解法中已经强调过。这里的本质原因是删除操作改变的是“当前节点的下一个节点”而不是“当前节点的位置”。当前指针一旦前进新的后继节点就可能被跳过。最后说全删除。此时链表所有节点都被删除返回nullptr。很多人会在这一步犹豫觉得应该返回原head或者什么特殊值。实际上没有任何特殊值删除完就是空链表返回nullptr就是正确结果。5.2 三种解法的复杂度对照解法时间复杂度空间复杂度代码量上手难度哨兵节点O(n)O(1)短低双指针O(n)O(1)中等中递归O(n)O(n)极短中从表格可以看出迭代解法在空间上全军覆没式的优势是工程中最常用的方案。面试时我建议优先写哨兵节点版本因为它好写、好讲、不易错。如果面试官追加提问“不用 dummy 怎么写”再用双指针版本兜底。5.3 变体题学会一道题拿下好几道LeetCode 203 虽然简单但它背后的删除套路可以迁移到很多兄弟题上。这里推荐三道练完之后你会意识到“哨兵节点”这个思路有多值钱。第一道是19. 删除链表的倒数第 N 个结点。解法是让一个指针先走 N 步再让两个指针同步走。走到末尾时第二个指针恰好停在前驱位置。但这里有个容易忽略的特殊情况如果删除的是头节点第二个指针还没有出发就已经结束了。用哨兵节点可以把这个特殊情况消掉。第二道是83. 删除排序链表中的重复元素以及它的加强版82. 删除排序链表中的重复元素 II。83 只需要保留一个重复值82 要求把重复值全部删掉。82 的难度明显上升因为你要判断的不再是“当前节点是否等于目标值”而是“当前节点和后继节点是否相等”。如果相等必须收集完所有重复节点再统一删除。这个逻辑非常适合用哨兵节点加双指针的组合来实现。第三道是707. 设计链表。这道题要求实现链表的增删改查相当于一次手工盖房子。等你在 707 里实现过addAtIndex和deleteAtIndex后再回头看 203会觉得一切都是水到渠成的事情。我在实际复盘时发现很多人的问题不是不会写某一道题而是不会把一道题里的思想提取出来。哨兵节点这个设计模式往小说是处理链表头部的边界情况往大说是一种“给数据结构增加统一接口”的思路。理解了这一层你再去刷上面那些变体题效率会明显不一样。
1. 题目本身很简单为什么很多人还是写不对LeetCode 203 移除链表元素是一道看起来人畜无害的基础链表题。给定一个单链表的头节点head和一个整数val删除链表中所有节点值等于val的节点最后返回新的头节点。这道题的难度标注是“简单”但我和一些候选人模拟面试时发现越是这种题越能暴露基本功。有人把所有等于val的节点删掉之后返回的还是旧head直接导致结果错误有人在头节点就是待删节点时逻辑分支写成一团乱麻还有人面对连续多个相同值的节点删了一个就跳出循环漏删了后面的。为什么一道基础题会踩这么多坑核心原因有两个一是链表删除本身涉及指针/引用的重连和数组删除的思维完全不同二是头节点没有前驱节点是一个天然的特殊情况很多人处理不好这个特殊情况就开始堆if来打补丁补到最后代码又长又容易错。这篇文章我会把这道题拆开揉碎地讲覆盖哨兵节点、双指针、递归三种主流解法然后把容易出错的边界条件单独拎出来分析最后再聊聊和它相关的几道高频变体题。适合刚接触链表、准备面试算法部分或者想加深对链表指针操作理解的读者。2. 哨兵节点解法用哑节点把特殊情况变成普通情况2.1 核心思路为什么我们需要一个虚拟节点链表的删除操作本质上就是一句话让前一个节点的next指向当前节点的next。问题在于头节点没有前一个节点。如果你要删除头节点就得单独处理“新的头节点是谁”的问题。很多人的第一反应是写两个分支先循环删除头部等于val的节点再处理中间节点。这确实能跑通但代码里出现了一类叫做“特判”的东西。特判越多代码逻辑的分支就越多出错概率越高。更优雅的做法是造一个哨兵节点dummy node把它放在真实头节点的前面。这个节点本身不存储业务数据它的唯一作用就是作为头节点的“前驱”。这样一来原来的头节点就变成了一个普通节点删除它和删除其他任何节点没有任何区别。遍历结束后真正的新头节点就是dummy-next。2.2 完整实现代码class Solution { public: ListNode* removeElements(ListNode* head, int val) { // 哨兵节点next 指向当前链表的头 ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { // 删除 cur-next跳过该节点 ListNode* toDelete cur-next; cur-next cur-next-next; delete toDelete; // 实际工程中记得释放内存 } else { cur cur-next; } } ListNode* result dummy-next; delete dummy; return result; } };这段代码里最关键的地方是cur指针一开始指向dummy而不是head。整个循环过程中我们检查的都是cur-next的值。如果它等于val就删除它如果不等于就把cur向后移动一位。2.3 一个特别容易忽略的操作细节在循环内部删除节点之后cur并没有移动。这不是漏写而是有意为之。因为删除cur-next之后新的cur-next是原来那个节点的后继。这个后继节点的值也可能等于val所以需要继续检查。举个例子链表是1 - 1 - 1 - 2val 1。一开始cur指向dummy发现dummy-next的值是 1删除它。此时dummy-next指向第二个值为 1 的节点。如果这时候顺手让cur往后走就会跳过这个节点导致漏删。所以“删除后不移动当前指针”是这段代码的核心纪律。基于常见实践我再补充一点LeetCode 的在线评测环境不要求手动释放内存但在实际工程里被删除节点的内存必须释放否则就是内存泄漏。上面的代码我加了delete toDelete如果是 Java 环境不需要这一步只需让cur-next cur-next-next剩下的交给垃圾回收。3. 双指针解法不借助哨兵显式维护前驱节点有些面试官会追问如果我不想用 dummy 节点你还能写吗这时候双指针解法就派上用场了。3.1 双指针的视角让前驱和后继关系清晰可见不用哨兵节点就要自己维护两个指针pre指向前一个节点cur指向当前正在检查的节点。初始时cur headpre nullptr。当cur-val val时需要让pre-next直接指向cur-next否则让pre cur然后cur cur-next。这个解法对初学者更友好因为它把链表删除的“前驱-当前-后继”三层关系直接摆在明面上。缺点是需要单独处理头节点因为pre一开始是空的没办法执行pre-next cur-next。3.2 实现代码class Solution { public: ListNode* removeElements(ListNode* head, int val) { // 先处理头节点连续等于 val 的情况 while (head ! nullptr head-val val) { ListNode* toDelete head; head head-next; delete toDelete; } if (head nullptr) return nullptr; ListNode* pre head; ListNode* cur head-next; while (cur ! nullptr) { if (cur-val val) { pre-next cur-next; ListNode* toDelete cur; cur cur-next; delete toDelete; } else { pre cur; cur cur-next; } } return head; } };这段代码写出来后很多人会问为什么中间那段处理逻辑没有走到pre因为在进入循环之前已经用while把头部的所有目标节点都删掉了。此时head一定不是待删节点pre才能安全地初始化为head。3.3 双指针解法最常见的翻车点我见过不少人在这个版本上犯一个错删除cur之后直接把cur cur-next然后再执行pre cur之类的操作导致前驱关系错乱。正确做法是删除分支里pre不动只移动cur非删除分支里pre和cur一起向后移动。这里有个容易混淆的点。很多人的直觉是“既然是双指针两个指针就该同步移动”。但删除场景里pre在删除动作发生后不能移动因为它的next刚刚被重新指向了一个新节点。如果pre也往后走就相当于跳过了这个新节点下次就无法检查它。为了帮助记忆可以把两个指针的分工记成一句话pre永远指向当前链表中“最后一个确认不需要删除的节点”cur则负责向前探索。当cur遇到需要删除的节点pre的next跳过它当cur遇到安全节点pre就追上来和cur保持相邻。4. 递归解法把删除操作交给函数调用栈4.1 另一种看待链表的视角迭代解法站在“从前向后遍历”的角度递归解法换了一个视角链表可以看作“当前节点 一个更短的链表”。删除所有值为val的节点等价于先处理掉后面那个短链表中的所有目标节点再根据当前节点的值决定要不要把它也删掉。这个思路的代码特别短短到第一次看到的人往往不敢相信它能通过。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; } };三行核心逻辑加一个递归基。处理完后续链表后如果当前节点的值等于val就跳过当前节点返回它的后继如果不等于就保留当前节点返回它本身。4.2 递归的执行过程拆解以链表1 - 2 - 6 - 3 - 4 - 5 - 6val 6为例。函数一路调用下去直到最后一个节点的next为nullptr开始逐层返回。最底层返回nullptr给值为 6 的节点这个节点发现自己的值和val相等于是把它后面的结果直接返回给上一个节点相当于删除了它自己。上一层是值为 5 的节点它的next接下来指向nullptr因为节点 5 的值不等于 6所以返回自身。就这样一层层往回组装被删除的节点彻底从链表中消失了。有一点需要强调递归里的head-next赋值是必要的。因为下一层递归可能调整了后继节点我们必须把返回结果接回去。如果漏掉这一行链表后半部分的修改就传不回来整个递归失效。4.3 递归解法的代价和适用范围递归解法写起来确实是最清爽的但它有一个不能忽视的代价空间复杂度是 O(n)。每次递归调用都会占用一个栈帧链表长度为 n 时调用深度也是 n。对于特别长的链表递归很可能导致函数调用栈溢出。在实际工程里我一般只在链表很短、或者数据结构本身就是递归定义比如树时才用递归。生产环境的高频链表操作还是迭代加上哨兵节点更稳妥。但面试时把递归解法写出来能证明你对链表结构有更深层的理解尤其是能用一句话解释清楚“为什么递归天然适合链表”这个问题会很加分。5. 边界条件梳理空链表、连续重复值、全删除5.1 容易被测试用例打脸的特殊场景LeetCode 的判题系统覆盖的边界条件非常全稍不注意就会在某一个用例上翻车。我自己把边界条件分成四类按危险程度排序场景示例风险点空链表head null直接返回 null不要访问任何节点头节点就是目标值[1,1,1,2],val1需要连续删除多个头节点所有节点都是目标值[7,7,7],val7删除后链表为空目标值在链表末尾[1,2,3],val3删除最后一个节点后遍历正确结束先说空链表。无论哪种解法第一件事都应该是判断head是否为空。递归解法里这对应递归基双指针解法里对应前面那段while循环后的空指针判断哨兵解法里由于dummy永远存在天然不会因为空链表崩溃但返回dummy-next时仍然是空的符合预期。再说连续重复值。在迭代解法里删除节点后不能立即让当前指针前进这个我在哨兵解法中已经强调过。这里的本质原因是删除操作改变的是“当前节点的下一个节点”而不是“当前节点的位置”。当前指针一旦前进新的后继节点就可能被跳过。最后说全删除。此时链表所有节点都被删除返回nullptr。很多人会在这一步犹豫觉得应该返回原head或者什么特殊值。实际上没有任何特殊值删除完就是空链表返回nullptr就是正确结果。5.2 三种解法的复杂度对照解法时间复杂度空间复杂度代码量上手难度哨兵节点O(n)O(1)短低双指针O(n)O(1)中等中递归O(n)O(n)极短中从表格可以看出迭代解法在空间上全军覆没式的优势是工程中最常用的方案。面试时我建议优先写哨兵节点版本因为它好写、好讲、不易错。如果面试官追加提问“不用 dummy 怎么写”再用双指针版本兜底。5.3 变体题学会一道题拿下好几道LeetCode 203 虽然简单但它背后的删除套路可以迁移到很多兄弟题上。这里推荐三道练完之后你会意识到“哨兵节点”这个思路有多值钱。第一道是19. 删除链表的倒数第 N 个结点。解法是让一个指针先走 N 步再让两个指针同步走。走到末尾时第二个指针恰好停在前驱位置。但这里有个容易忽略的特殊情况如果删除的是头节点第二个指针还没有出发就已经结束了。用哨兵节点可以把这个特殊情况消掉。第二道是83. 删除排序链表中的重复元素以及它的加强版82. 删除排序链表中的重复元素 II。83 只需要保留一个重复值82 要求把重复值全部删掉。82 的难度明显上升因为你要判断的不再是“当前节点是否等于目标值”而是“当前节点和后继节点是否相等”。如果相等必须收集完所有重复节点再统一删除。这个逻辑非常适合用哨兵节点加双指针的组合来实现。第三道是707. 设计链表。这道题要求实现链表的增删改查相当于一次手工盖房子。等你在 707 里实现过addAtIndex和deleteAtIndex后再回头看 203会觉得一切都是水到渠成的事情。我在实际复盘时发现很多人的问题不是不会写某一道题而是不会把一道题里的思想提取出来。哨兵节点这个设计模式往小说是处理链表头部的边界情况往大说是一种“给数据结构增加统一接口”的思路。理解了这一层你再去刷上面那些变体题效率会明显不一样。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
