1. 题号背后的乌龙LeetCode 98 与链表的真实对应关系先把话放在前面这个标题里有个小坑。LeetCode 官方题库里第 98 题是《Validate Binary Search Tree》验证二叉搜索树考的是二叉树中序遍历是否严格递增跟链表删除节点八竿子打不着。真正对应「从链表中移除在数组中存在的节点」这个描述的是 LeetCode 3217《Delete Nodes From Linked List Present in an Array》。我猜题目来源可能是某个刷题平台的自定义题号或者复制题目时串行了。这其实也提醒了一件事刷题时不要只看题号要认题目描述本身不然对着 98 题准备半天链表操作打开编辑器发现是中序遍历心态直接崩。下面我按「从链表中移除在数组中存在的节点」这道题来展开题号我们后面统一按 LeetCode 3217 来称呼。这道题在业界评价里属于「medium 偏 easy」的区间非常典型数组负责提供查找条件链表负责提供删除场景。坦白说链表的删除操作本身你翻任何一本数据结构教材都能找到 C 语言伪代码但一旦跟数组、哈希表、指针边界条件搅在一起很多人在周赛里还是会写出各种奇怪的 bug。我见过有人在 while 循环里忘记更新 prev结果链直接断成两截的也有人把数组重复元素当成需要去重的对象白白多写几十行代码。这篇文章就围绕这道题来拆解从读题、暴力解到哈希表优化再到哑节点的使用、完整代码、复杂度推导最后聊聊这题能延伸出哪些变种。不管你是准备面试还是单纯练手看完应该能一次把链表删除 哈希表这套组合拳打熟。2. 从题目描述里提取的三个关键信号2.1 链表单向、不带头节点、值可能重复题目的核心输入是一个单链表的头节点head链表节点结构通常是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) {} };注意三个隐含条件第一head是首元节点而不是头节点也就是说第一个节点就有实际数据第二链表是单向的你没法回头找前驱第三题目没有明确说节点值是否唯一所以最好当成可能有重复值来处理。为什么说第三个信号重要因为如果节点值允许重复那么删除条件就变成「只要节点值出现在数组里就全部删掉」不能用「删第一次就停」。虽然哈希集合天然去重但这个逻辑要想清楚。2.2 数组只做「存在性判断」不做计数和索引nums数组在这里的角色特别单纯它不要求你返回数组下标不要求统计出现次数只问「这个节点的值在不在数组里」。这意味着数组本身的长相是否有序、是否重复、长度多大都不重要重要的是怎么快速回答「在不在」。这种「在不在」查询天生就是哈希表的舒适区。当然如果数组长度很小比如 n ≤ 100直接两层循环暴力查也能过但面试官问一句「复杂度多少」你就得老实说O(m*n)。后面会展开讲什么时候换哈希表什么时候其实不用换。2.3 删除必须维持剩余节点的相对顺序删除链表节点的本质是绕过被删节点让前驱直接指向后继。题目要求最终链表依然保持原来的相对顺序所以不能用「把保留节点的值收集到数组再重建链表」这类取巧办法——虽然结果对但完全没练到链表操作面试官大概率会让你重新写。来看一个具体例子。假设链表是1 - 2 - 3 - 4 - 5数组是[1, 2, 3]那么删除后应该得到4 - 5。如果头节点也被删了那么新的头节点会变成第一个没被删的节点这个边界情况后面专门讨论。3. 从暴力解到哈希表为什么说数组只配当陪跑3.1 暴力解法复杂度失控的典型最直观的思路是遍历链表对每个节点再遍历一遍数组判断值是否相等。伪代码如下ListNode* removeNodes(ListNode* head, vectorint nums) { // 第一层循环遍历链表 while (遍历到每个节点) { bool found false; for (int x : nums) { if (x 当前节点值) { found true; break; } } if (found) 删除当前节点; } return head; }这里有两个致命问题。第一个问题是复杂度。链长设为m数组长度设为n最坏情况下每个节点都要把整个数组扫一遍时间复杂度O(m*n)。在 LeetCode 的测试数据下m和n都可能到10^4甚至10^510^5 * 10^5 10^10次比较超时没商量。即使不打竞赛工程上这种双重循环的判断方式也是低效的典型。第二个问题是删除逻辑变啰嗦。因为暴力解法里for循环提前break了你只是知道了「在不在」真正要删节点时还得再处理一遍指针。你会发现代码越写越长全是边界处理核心思路反而被淹没。这就是「数据结构不合适时连操作都变得费劲」的经典案例。3.2 哈希表优化拿空间换时间的教科书操作既然数组只回答「在不在」那就把所有数组元素塞进哈希集合。C 用unordered_setJava 用HashSetPython 用set都行。查询均摊O(1)于是总复杂度变成O(m n)unordered_setint st(nums.begin(), nums.end());这只是预处理一行代码。之后遍历链表时每个节点查一次集合查不到就保留查到了就删除整段流程非常干净。有人会问哈希碰撞导致最坏情况下退化到O(n)是不是不严谨理论上是的但工程实现上哈希表有负载因子控制和冲突处理策略实际表现就是均摊常数级。面试时如果你主动说出「均摊 O(1)」反而显得你了解底层的哈希设计这里的一个隐藏加分点后面会提一句怎么用数组值域压缩来彻底绕过哈希碰撞。3.3 什么时候可以不换哈希表经验之谈如果nums数组特别小长度不到 50暴力解法在真实机器上可能跟哈希表差不多快甚至更快——因为unordered_set的哈希计算和内存分配也有开销。LeetCode 题目不会给你这种优惠直接上哈希表最稳妥。但如果面试中改成「只能使用 O(1) 额外空间」那就要换个思路先把数组排序然后遍历链表时用二分查找判断「在不在」时间复杂度O(m*log n)。这也是个合理方案适合作为和面试官讨论的加餐。4. 链表删除的经典陷阱哑节点、前驱、移动顺序4.1 头节点删除的边界哑节点的真正价值链表删除最闹心的永远是「如果头节点要删怎么办」。不带头节点的单向链表删除头节点意味着head指针本身要变删除中间节点只需要改前驱的next。这两件事逻辑不统一写起来容易出 bug。初级写法是先循环处理头部把连续要删的头节点全部清掉然后进入常规的双指针删除循环while (head st.count(head-val)) { head head-next; } ListNode* prev head; while (prev prev-next) { if (st.count(prev-next-val)) { prev-next prev-next-next; } else { prev prev-next; } } return head;这套逻辑没问题但两个 while 循环、两个分支看起来不够紧凑。更优雅的做法是引入哑节点dummy nodeListNode* dummy new ListNode(0, head); ListNode* prev dummy; while (prev-next) { if (st.count(prev-next-val)) { prev-next prev-next-next; // 删除后 prev 不移动 } else { prev prev-next; // 未删除才移动 } } return dummy-next;哑节点的好处让头节点变成「和其他节点一样的中间节点」统一了删除逻辑不再需要单独处理head。这也是为什么我在刷题和工程代码里都习惯挂一个哑节点——写出来的代码几乎不会被边界情况偷袭。4.2 指针什么时候该动最容易错的细节上面代码里最容易错的是prev的移动逻辑。很多人第一时间写出来的版本是if (st.count(prev-next-val)) { prev-next prev-next-next; prev prev-next; // 错 }为什么错因为prev-next-next是「被删节点的后继」而它可能也是需要被删的节点。如果删除后立刻把prev移到后继上那么后一个节点就被跳过了——它还没被检查就会从链上漏过去。正确姿势只有一个口诀删了不动没删才动。删除分支里只改prev-nextprev自己原地待命只有当前节点不需要删除时prev才往前走一步。这样下一个循环会重新检查新的prev-next不重不漏。4.3 保存旧指针的问题内存安全与野指针C 选手必须额外注意一件事删除节点时如果直接prev-next prev-next-next那个被删节点就没有任何指针指向它了但它还占着堆内存。严谨的做法是先把要删的节点存下来改完指针后deleteListNode* toDelete prev-next; prev-next prev-next-next; delete toDelete;LeetCode 的在线评测环境一般不检查内存泄漏每跑完一个用例就销毁整个进程但工程上这是基本功。你要是面试手写代码时可以主动提「这里需要 delete否则内存泄漏」绝对是加分项。Python 选手不用手动管但要注意prev-next-next这个表达式读起来也别绕进去理解指针变化比语言层面的内存管理更重要。4.4 空链表的处理别在最后一道防线翻车如果head本身是空指针任何指针操作都要直接返回空。用了哑节点之后while (prev-next)天然会跳过空链表所以不会崩这是哑节点的另一个隐藏保护。写代码时最好心里有个 checklist空链表、头节点被删、所有节点都被删、链表只有一个节点——四个场景跑一遍基本就稳了。5. 双语言完整实现与复杂度推导5.1 C 实现class Solution { public: ListNode* removeNodes(ListNode* head, vectorint nums) { unordered_setint st(nums.begin(), nums.end()); ListNode* dummy new ListNode(0, head); ListNode* prev dummy; while (prev-next) { if (st.count(prev-next-val)) { ListNode* toDelete prev-next; prev-next prev-next-next; delete toDelete; } else { prev prev-next; } } ListNode* result dummy-next; delete dummy; return result; } };这段代码已经考虑了内存释放toDelete保存被删节点并delete最后dummy也释放掉。做题环境下删不删dummy无所谓但养成好习惯不亏。5.2 Python 实现class Solution: def modifiedList(self, head: Optional[ListNode], nums: List[int]) - Optional[ListNode]: num_set set(nums) dummy ListNode(0, head) prev dummy while prev.next: if prev.next.val in num_set: prev.next prev.next.next else: prev prev.next return dummy.nextPython 版本更简洁核心逻辑一样prev原地判断删除分支不移动。要注意set(nums)的构建是O(n)in操作均摊O(1)整体复杂度与 C 版本相同。5.3 复杂度推导不要只背结论设链表长度为m数组长度为n。构造哈希集合遍历数组一次O(n)时间和O(n)额外空间排序去重法可以降空间但升时间属于 trade-off。遍历链表每个节点至多被检查一次被删除的节点至多被「跳过」一次所以是O(m)时间。总时间复杂度O(m n)。这是单次遍历达到的下限你不能比这个更快了因为你至少得把数组和链表各看一遍。空间复杂度O(n)主要开销是哈希集合。如果有人问「能不能做到 O(1) 空间」答案是可以但需要改变处理顺序先对nums原地排序O(log n)空间用于递归栈然后遍历链表时用二分查找每查一次O(log n)总时间O(m log n)。这个方案在面试中作为备选方案提出来显得你考虑过空间约束的不同组合。6. 这题还能延伸出哪些变种从周赛到工程实践的跨度6.1 变种一循环单链表怎么处理如果题目改成「给定一个循环单链表删除数组中存在的节点」核心难点从「边界处理」变成「终止条件」。循环链表没有nullptr结尾你不能用while (prev-next)作为循环条件否则会无限转圈。常见做法是先找到任意一个「确定不需要删除」的节点作为锚点然后从它的下一个节点开始遍历回到锚点时停止。如果整个链表的节点值全在数组里那就没有锚点得返回一个「空循环链表」——这里反而要小心空和「单节点且被删」是两种表现。这个变种在周赛里出现的频率不低考的就是你对循环链表终止条件的理解。6.2 变种二数组很大但值域有限时用布尔数组替代哈希如果题目约束0 node.val 100000很多链表题确实给这种范围你可以直接用vectorbool或bitset做标记把数组元素对应位置设为true。这样连哈希都不需要查询是真正的O(1)且没有碰撞问题vectorbool exists(100001, false); for (int x : nums) exists[x] true; // 之后判断 if (exists[curr-val])空间是固定的O(V)V是值域如果值域小这比unordered_set更省心。我在项目里处理「大量 ID 黑名单」时也用过类似思路如果 ID 是整数且范围可控一个vectorbool比unordered_set快得多内存也更紧凑。6.3 变种三不只是删除还要按数组顺序重排有些题目会反过来给你一个链表和一个数组要求只保留数组中存在的节点并且按数组中的顺序排列。这就变成另一道题了因为你不能只做删除还得涉及链表的拆分、暂存、按序重建。核心还是哈希表判断 链表基本功但复杂度会从一遍遍历变成两到三遍。刷完本题后可以顺手想想这个方向链表题的套路就那些组合来组合去都在考基本功。6.4 和「删除排序链表重复节点」对比理解LeetCode 82 / 83 是删除排序链表中的重复节点。那类题有一个天然优势链表本身有序重复节点必然相邻所以不需要额外哈希表只要相邻比较就行。但本题的删除条件是「数组里的值」这个条件与链表顺序无关所以必须借助哈希表提供全局查询能力。理解这个差异你就明白了凡是「无关顺序的集合判断」第一步就该想哈希表凡是「顺序相邻的关系判断」试试指针滑动能不能解决。6.5 周赛语境下的实战建议如果你是在周赛里遇到这题LeetCode 周赛 430 附近出现过类似难度的链表题实战建议是先把暴力法在草稿纸上写出来确认超时然后立刻切换哈希表全程控制在 5 分钟内。链表题最忌讳一上来就写链表操作结果数组那边的数据结构都没定型越写越乱。顺序应该是确定查询方案哈希/布隆筛选/值域数组→ 确定删除策略哑节点 双指针→ 最后才是细节编码。7. 我自己在反复刷这题之后的几点体会我刷这道题前前后后写过五个版本暴力双重循环、排序后二分、哑节点 unordered_set、哑节点 值域布尔数组、以及循环链表的变种实现。写完之后最大的体会是链表的题目永远不在「会不会写 while」而在「边界条件是否在写代码之前已经被大脑处理过一遍」。这道题里prev移动的时机、头节点的统一处理、空链表保护这三件事如果能闭着眼写对那你在链表题上的基本功基本合格了。别小看这种看起来「简单到不值得刷」的题面试时紧张的场景下手抖写错prev prev-next放在哪个分支的候选人我见过不止一个。最后分享一个调试小技巧如果链表删除题结果不对先在纸上画三个节点的链表用箭头把prev的每一步移动标出来对照代码走一遍。比在 IDE 里打断点快得多。链表题的 bug 九成出现在「你以为指针动了其实没动」或者「你以为没动其实动了」。画箭头一目了然。