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, vector<int>& 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^5，10^5 * 10^5 = 10^10次比较，超时没商量。即使不打竞赛，工程上这种双重循环的判断方式也是低效的典型。
第二个问题是删除逻辑变啰嗦。因为暴力解法里for循环提前break了，你只是知道了「在不在」，真正要删节点时还得再处理一遍指针。你会发现代码越写越长，全是边界处理，核心思路反而被淹没。这就是「数据结构不合适时连操作都变得费劲」的经典案例。
3.2 哈希表优化：拿空间换时间的教科书操作
既然数组只回答「在不在」，那就把所有数组元素塞进哈希集合。C++ 用unordered_set，Java 用HashSet，Python 用set，都行。查询均摊O(1)，于是总复杂度变成O(m + n)：
unordered_set<int> 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 node）：
ListNode* 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->next，prev自己原地待命；只有当前节点不需要删除时，prev才往前走一步。这样下一个循环会重新检查新的prev->next，不重不漏。
4.3 保存旧指针的问题：内存安全与野指针
C++ 选手必须额外注意一件事：删除节点时，如果直接prev->next = prev->next->next，那个被删节点就没有任何指针指向它了，但它还占着堆内存。严谨的做法是先把要删的节点存下来，改完指针后delete：
ListNode* 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, vector<int>& nums) { unordered_set<int> 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（很多链表题确实给这种范围），你可以直接用vector<bool>或bitset做标记，把数组元素对应位置设为true。这样连哈希都不需要，查询是真正的O(1)，且没有碰撞问题：
vector<bool> exists(100001, false); for (int x : nums) exists[x] = true; // 之后判断 if (exists[curr->val])空间是固定的O(V)（V是值域），如果值域小，这比unordered_set更省心。我在项目里处理「大量 ID 黑名单」时也用过类似思路：如果 ID 是整数且范围可控，一个vector<bool>比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 九成出现在「你以为指针动了，其实没动」或者「你以为没动，其实动了」。画箭头，一目了然。
