刷 LeetCode 刷到这道 98 题的时候我愣了一下。倒不是因为难度——题目本身不算难而是它把“链表”和“数组”这两个最基础的数据结构揉在了一起还要求在数组里查节点值。很多人在链表删除上熟门熟路但一碰到“数组里存在”这个条件第一反应就是 for 循环写完才发现复杂度爆了。这道题的标准表述是给定一个链表头节点 head 和一个整数数组 nums删除链表中所有值在 nums 中出现的节点返回新的头节点。听起来简单但动手写的时候至少有三个细节值得展开说清楚怎么快速判断数组里有没有这个值、怎么处理头节点被删的情况、以及怎么保证指针操作不把链表搞断。这篇文章我会从题目拆解开始讲清楚每一步的思考过程给出 Java 和 C 两版可以直接跑的完整代码再把我实际刷题和帮别人 review 代码时踩过的坑、排查过的 bug 全部列出来。不管你是在备战面试还是在补数据结构的底子这篇都值得看完。1. 题目拆解与解题思路到底在考什么1.1 先看题目本质这是一道“值删除”而非“索引删除”的题链表删除节点一般有两种模式按索引删除删除第 k 个节点这个比较简单走 k-1 步就能找到前驱。按值删除删除所有值等于某个 target 的节点通常需要遍历链表逐个比对。这道题就是典型的按值删除只不过 target 不是一个值而是一整批值数组里的所有元素。所以它的本质是遍历链表一次对每个节点判定“当前节点的值是否在给定集合中”如果在就把它从链表里摘掉。很多新手容易踩的第一个坑就是用 for 循环遍历数组判断。假设链表的长度是 m数组长度是 n那最直观的双重循环时间复杂度就是 O(m×n)。如果 m 和 n 都到 10^5 级别这个量级直接就超时了。面试官看到这种写法基本第一轮就给你打回去了——倒不是说双重循环一定不能过而是它暴露了一个问题你没有建立“批量判断”的思维。1.2 为什么用哈希集合空间换时间的经典选择要在 O(1) 时间内判断一个值在不在数组里最自然的做法就是把数组转成一个哈希集合Java 里是 HashSetC 里是 unordered_set。这样整体时间复杂度的瓶颈就只剩遍历链表本身也就是 O(m)。额外空间复杂度是 O(n)用来存数组里那些值。有个细节值得注意数组里的元素可能有重复。比如 nums [1, 1, 2, 3]如果用 HashSet重复的 1 会被自动去重这反而帮了我们——因为链表节点的值只需要判断“在不在集合里”不需要计数。所以这一步对最终结果没有任何影响但如果你用数组标记法比如布尔数组就得额外处理值域范围的问题了。1.3 直观方案对比暴力法 vs 哈希法我用表格把几种方案的思路和代价列一下方便对比方案核心思路时间复杂度空间复杂度适用场景双重循环每遍历一个链表节点就 for 扫描数组O(m×n)O(1)数组很小比如长度 100哈希集合数组转 HashSet遍历链表 O(1) 查值O(mn)O(n)通用场景面试标准答案排序后双指针数组排序链表遍历时用二分/双指针O(m log n n log n)O(1)要求不能用额外空间时布尔标记数组值域已知且较小时用 boolean[] 直接映射O(mn)O(值域)值域连续且可控如 0~1000面试时首选哈希方案因为它在时间和空间上最均衡而且代码简短、不易出错。排序后双指针那个方案我更建议作为面试时的“加分延伸”提一嘴显示你不是只会背模板这个后面会细讲。2. 核心细节解析哨兵节点、指针顺序与内存问题2.1 哨兵节点解决“头节点被删”的通用套路链表的头节点很特殊它没有前驱。如果头节点的值恰好要删除你就得更新头指针。不少人会写一堆 if 判断来单独处理头节点比如先 while 循环把头节点删干净直到 head 的值不在集合里。然后处理中间节点。这样确实能过但代码很丑而且容易漏。比如头节点连着删了好几个while 条件写错了就会空指针。更优雅的做法是加一个哨兵节点dummy / sentinel也就是创建一个虚拟节点让它指向头节点。这样一来原来的头节点也有前驱了所有删除操作都统一成“处理某个节点的后继”不需要再区分头节点和中间节点。最终返回 dummy.next 就行不管头节点被删没删dummy.next 永远指向新的头。2.2 指针操作的先后顺序先判断、再删除、后移动拿到链表题我习惯先在纸上画出节点之间的关系再动手写。比如当前遍历到的节点是 cur如果 cur.next 的值要删除操作就三步让 cur.next 指向 cur.next.next也就是跳过那个要删的节点。在 C 里这一步之前得先保存 deleterNode跳完之后 delete 掉避免内存泄漏。注意这一步不要移动 cur因为新的 cur.next 还没检查过可能也是要删的。如果你在删除节点之后立刻执行 cur cur.next那就会漏掉新的 cur.next。这个 bug 特别隐蔽我第一次写的时候就是在这个地方踩的坑——链表中间有两个连续需要删除的节点结果只删了第一个。2.3 语言差异Java 的 GC 和 C 的手动释放Java 里不用管删除节点的内存释放JVM 的垃圾回收会自动处理不可达对象。所以代码写起来很干净一个指针跳过去就算删完了。C 就没那么轻松了。虽然 LeetCode 的评测环境对内存泄漏不敏感但面试时如果写了 C面试官很可能会问“你删掉的节点不释放吗”所以我在 C 版本里加了 delete 操作这也是一个值得刻意练习的好习惯。3. 完整代码实现与逐段拆解3.1 Java 版本简洁、可读、可直接 ACclass Solution { public ListNode removeElements(ListNode head, int[] nums) { // 基础检查链表为空就直接返回 null if (head null) { return null; } // 用 HashSet 装数组里的值查询是 O(1) SetInteger toDelete new HashSet(); for (int val : nums) { toDelete.add(val); } // 哨兵节点避免头节点单独处理的逻辑 ListNode dummy new ListNode(0); dummy.next head; ListNode cur dummy; while (cur.next ! null) { if (toDelete.contains(cur.next.val)) { // 跳过要删除的节点 cur.next cur.next.next; } else { // 当前后继不用删才移动到下一个位置 cur cur.next; } } return dummy.next; } }代码量不大核心就是那两行指针操作。我第一次写的时候顺序写反了把 cur cur.next 放在了 if 外面导致连续删除时漏掉了后面的节点。可以让读者特别注意注释里的那一行只有不需要删除当前后继时才能让 cur 前进。3.2 C 版本带内存释放的完整实现class Solution { public: ListNode* removeElements(ListNode* head, vectorint nums) { if (head nullptr) { return nullptr; } unordered_setint toDelete(nums.begin(), nums.end()); ListNode dummy(0); dummy.next head; ListNode* cur dummy; while (cur-next ! nullptr) { if (toDelete.count(cur-next-val)) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; // 手动释放避免内存泄漏 } else { cur cur-next; } } return dummy.next; } };C 版本里有个细节哨兵节点我选择在栈上建ListNode dummy(0)而不是 new 一个指针。这样就不需要手动释放 dummy少了一处可能泄漏的地方。如果你习惯 new ListNode(0)记得在返回前 delete dummy——但那样容易踩到别的坑我建议直接在栈上声明。3.3 复杂度分析为什么这个方案能过因为是单次遍历链表每个节点的处理时间都是 O(1)所以时间复杂度是 O(mn)其中 m 是链表长度n 是数组长度。空间上HashSet 存了数组的元素额外占用 O(n) 空间。面试的时候你可以主动把这个复杂度分析讲出来然后补一句“如果数组很大而链表很小其实 O(n) 的空间是可以接受的。如果要求严格 O(1) 空间可以把数组排序后用双指针法扫描链表和数组但那样会修改原数组需要事先跟面试官确认。”这句话一出基本就稳了。4. 常见问题与排查技巧实录4.1 问题一连续节点被删结果只删了一个这是我自己的亲身经历。一开始我是这样写的while (cur.next ! null) { if (toDelete.contains(cur.next.val)) { cur.next cur.next.next; } cur cur.next; // 这里错了 }链表是 1 - 2 - 2 - 3nums [2]。理想结果是 1 - 3。但上面这段代码跑出来是 1 - 2 - 3。原因就是删掉第一个 2 之后cur 已经指向了原来的第二个 2此时 cur.next 是 3不再检查 2 了所以第二个 2 就漏掉了。修复方式很简单只有 cur 的后继不需要删除时cur 才前进。也就是上面完整代码里写的那样。这个错误出现频率极高。我帮不少人 review 过链表题十个里至少有四个犯过这个问题。记住一句话删了一个节点之后原地不要动检查新的 next。4.2 问题二数组为空或者链表为空空数组其实不影响逻辑toDelete 是个空集合所有 contains 都是 false链表原样返回。空链表也提前兜住了直接在开头返回 null。但有一个边界容易被忽略链表只有一个节点且它恰好要被删除。这种情况哨兵节点就发挥作用了——dummy.next 直接变成 null返回 null代码没有任何分支处理。如果不用哨兵这种单节点自删的 case 很容易写成访问空指针特别是在 C 里直接崩给你看。4.3 问题三Java 里 HashSet 含 null这道题里数组可能包含 null 吗题目如果没说默认是整数数组不会。但如果你用泛型 Set 而不是原始类型的专项集合万一数组里真有个 nullHashSet 是允许存 null 的contains(null) 返回 true那么所有为 null 的节点都会被删。对于这道 LeetCode 题来说链表节点的 val 是 int数组也是 int不存在这个问题。但如果你是拿这套代码去改造成通用节点的业务代码比如删掉配置里指定的某些用户要注意这个细节。4.4 问题四内存泄漏与悬空指针C 面试里悬空指针是高频追问点。我上面 delete tmp 之后tmp 指针自己还在如果你再用 tmp-val 就 UB 了。所以 delete 之后可以顺手 tmp nullptr。当然LeetCode 的在线评测一般不会检查内存泄漏所以日常刷题时写不写 delete 都能过。但面试场景下特别是视频面试手撕代码面试官会盯你的 C 代码风格。我建议平时就养成及时释放的好习惯面试时就能自然写出来。4.5 常见问题速查表症状可能原因解决办法连续两个相同值的节点只删了一个删除后 cur 自动前移了只有不需要删除时才 cur cur.next头节点被删时返回结果不对没有统一处理头节点加哨兵节点 dummy运行超时用数组遍历代替哈希查询转成 HashSet/unordered_setC 版本内存持续增长删节点未释放内存delete 被跳过的节点空链表报错没在开头处理 headnull先行判断返回 null5. 变体与延伸面试追问怎么答5.1 如果题目改成“删除链表中所有在数组中出现的节点并返回新链表的头”题目原文其实就是要求原地删除返回原链表的头。但如果改成不修改原链表而是构建一个新链表返回思路就更简单了遍历原链表逐个判断当前节点的值是否在哈希集合中。不在集合中的节点尾插法接入新链表尾部。这种变体的好处是不需要考虑哨兵节点、不需要处理删除时的指针细节但多一份空间开销来建新链表。面试时提到这种思路可以展示你“知道多种方案并能为不同需求选型”的能力。5.2 如果要求空间复杂度降到 O(1)这是面试里常见的进阶追问。思路是先把数组排序然后用双指针扫描有序数组和链表。每走到一个链表节点就用二分查找或双指针推进判断它的值在不在数组里。这个方案空间是 O(1)但代价是排序数组 O(n log n)。如果数组本身就是乱序且很大排序的开销可能超过了哈希的额外空间开销。所以我会在面试时做个权衡分析数据规模多大用哈希、什么情况下排序更划算。以我目前看到的面试题情况来看能主动在标准解法之外讨论这个 trade-off 的候选人给面试官留下的印象会好很多。5.3 如果把链表改成循环链表题目给了扩展的可能。如果是循环单链表需要注意终止条件从 cur.next ! null 变成 cur.next ! head同时哨兵节点和返回值都要调整。循环链表删除节点还有一个额外难点如果要删除的节点包含尾节点你可能会面临“收回尾节点后需要更新头指针”的情况。不过这些属于锦上添花的内容我建议先把基础写法练熟再考虑这些变体。面试官如果真问到了能说出循环链表与普通链表在终止条件上的差异就已经说明你对链表遍历有深入理解了。5.4 如果数组变成“千万级”大数组哈希集合的空间是 O(n)千万个整数大概占几十 MB 内存在力扣服务器上通常可以接受。但在真实业务里如果被删节点列表是从数据库读出来的千万级 ID 集合你要考虑的不再是算法复杂度而是 JVM 堆大小和 GC 压力。真遇到这种场景一是可以考虑 BitSet 按位标记如果 ID 范围可控二是直接批量分批过滤三是考虑内存数据库或布隆过滤器。当然这些偏工程化的优化对刷题来说可能超纲了但知道有这些方向能让你在技术讨论时多几个角度。6. 刷题心法我从这道题里总结的三条经验第一链表题先画图再写代码。我每次做链表题都会在草稿纸上画出 dummy、head、cur 这三个指针的指向关系删除前后的变化一目了然。凡是直接上手写的我十次有八次要改 bug。画图 30 秒debug 少十分钟这买卖划算。第二数组相关的优化优先想“查找方式”。凡是碰到“数组里是否存在”这类判断先别急着写 for想一想数据规模能不能用 HashSet、能不能排序后二分、能不能用 BitSet。这种条件反射练多了很多题型的思路都会打开。第三AC 之后别着急下一题。花十分钟想一想代码里有什么边界情况删掉哨兵节点会不会更麻烦换成 C 怎么处理内存面试官最可能追问哪个点把这些问题想一遍一道简单题就能榨出三五道题的价值。我自己的刷题节奏是一天搞定三五道题不求多但求每道都吃透。这道题虽然不算难但它串起了链表遍历、哈希应用、指针操作、边界处理和内存管理五个知识点算是一个性价比很高的练习题。如果你刚入门链表建议把这道题和“移除链表元素”“删除排序链表中的重复元素”放在一起练能形成一个完整的链表删除题组举一反三的效率会高不少。