从链表中移除在数组中存在的节点 图解题解
这道题到底在问什么
- 输入
- nums = [1,2,3], head = [1,2,3,4,5]
- 输出
- [4,5]
- 输入
- nums = [3,5,7], head = [3,1,5,2,7,4]
- 输出
- [1,2,4]
最优解：一步一步想明白
- 3记牢这套动作:prev 盯着自己的下一个节点,命中集合就断链跳过、prev 原地不动;没命中才让 prev 前进一格。哨兵的作用是让删头节点也走这同一套逻辑。下面从哨兵开始扫。
- 4先把这条链表看清楚。从左到右 6 个节点,值依次是 3、1、5、2、7、4。最左边那个写着 D 的方块是我等下要接上的哨兵,先别管它。任务是把值等于 3、5、7 的节点全删掉。
- 5第一步,把 nums 里的 3、5、7 全塞进一个哈希集合 s。为什么不直接在 nums 里一个个找?因为那样每查一次都要扫一遍 nums,太慢。装进集合后,问一个值在不在里面,基本是一瞬间的事。
- 6第二步,在真正的头节点 3 前面接一个哨兵 D,再让前驱指针 prev 站在 D 上。有了哨兵,哪怕头节点要删,也能靠 prev 从前面把它跳过去,不用为删头单独写一套代码。现在 prev 的下一个,正是链表第一个节点 3。
- 7一切就位。集合建好了,哨兵接上了,prev 站在哨兵上。接下来就重复一个动作:只要 prev 后面还有节点,就拿它的值去问集合。我们从 prev 的下一个,也就是节点 3,开始。
- 8prev 现在停在 哨兵 D,它的下一个节点值是 3。拿这个 3 去问集合 {3, 5, 7}:你在不在里面?在,这个节点得删。
- 93 确实在集合里,那就把它摘掉:让 哨兵 D 的指针越过 3,直接接到它后面那个节点。3 就此从链上掉队,变灰。注意 prev 这时候一步都不能挪,因为新接上来的节点还没查过,得原地接着看它。
- 10摘除完成。现在 哨兵 D 后面接上的是 1,prev 依旧停在原地。目前为止删掉的是 3。下一轮就轮到查这个新接上来的 1 了。
- 11prev 现在停在 哨兵 D,它的下一个节点值是 1。拿这个 1 去问集合 {3, 5, 7}:你在不在里面?不在,这个节点要留下。
- 121 不在集合里,是要留下的节点,标成蓝色。这时候 prev 才往前走一格,踩到 1 上,准备去看它后面的节点。到目前为止保下来的是 1。
- 13prev 现在停在 1,它的下一个节点值是 5。拿这个 5 去问集合 {3, 5, 7}:你在不在里面?在,这个节点得删。
- 145 确实在集合里,那就把它摘掉:让 1 的指针越过 5,直接接到它后面那个节点。5 就此从链上掉队,变灰。注意 prev 这时候一步都不能挪,因为新接上来的节点还没查过,得原地接着看它。
- 15摘除完成。现在 1 后面接上的是 2,prev 依旧停在原地。目前为止删掉的是 3、5。下一轮就轮到查这个新接上来的 2 了。
- 16prev 现在停在 1,它的下一个节点值是 2。拿这个 2 去问集合 {3, 5, 7}:你在不在里面?不在,这个节点要留下。
- 172 不在集合里,是要留下的节点,标成蓝色。这时候 prev 才往前走一格,踩到 2 上,准备去看它后面的节点。到目前为止保下来的是 1、2。
- 18prev 现在停在 2,它的下一个节点值是 7。拿这个 7 去问集合 {3, 5, 7}:你在不在里面?在,这个节点得删。
- 197 确实在集合里,那就把它摘掉:让 2 的指针越过 7,直接接到它后面那个节点。7 就此从链上掉队,变灰。注意 prev 这时候一步都不能挪,因为新接上来的节点还没查过,得原地接着看它。
- 20摘除完成。现在 2 后面接上的是 4,prev 依旧停在原地。目前为止删掉的是 3、5、7。下一轮就轮到查这个新接上来的 4 了。
- 21prev 现在停在 2,它的下一个节点值是 4。拿这个 4 去问集合 {3, 5, 7}:你在不在里面?不在,这个节点要留下。
- 224 不在集合里,是要留下的节点,标成蓝色。这时候 prev 才往前走一格,踩到 4 上,准备去看它后面的节点。到目前为止保下来的是 1、2、4。
- 23prev 现在停在最后保留下来的节点 4,它后面已经没有节点了,prev.next 是空。这就是循环的终点。返回哨兵的下一个,也就是新链表真正的头。
- 24回头看全程。灰掉的 3、5、7 是命中集合被摘掉的,蓝色的 1、2、4 是一路留下来的。把蓝色节点顺次连起来,就是最终链表 1、2、4。整趟只从头到尾走了一遍,靠哨兵和前驱指针把删头、删中间统一成同一套动作。
⚠️ 容易写错的地方
✗ 错：命中删除后让 prev 也跟着前进
✓ 对：删除时 prev 原地不动,只有保留才前进
删掉 prev.next 后,新接到 prev 后面的节点还没检查过,若 prev 跟着走会直接跳过它,可能漏删一个该删的节点
✗ 错：不接哨兵,直接从 head 开始删
✓ 对：在 head 前接一个哨兵节点统一处理
头节点也可能要删,不用哨兵就得为删头写一段特判;有了哨兵,删头和删中间是同一套 prev.next 越过的动作
✗ 错：每次都在 nums 里线性查找是否存在
✓ 对：先把 nums 装进哈希集合再查
链表长 n、nums 长 m,逐次线性查是 O(n 乘 m),数据大了会超时;哈希集合把单次查询压到常数,总体降到 O(n 加 m)
✗ 错：返回原来的 head
✓ 对：返回 dummy.next
如果头节点被删了,原来的 head 已经不在链上;哨兵的 next 永远指向当前真正的头,返回它才对
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def modifiedList(
self, nums: List[int], head: Optional[ListNode]
) -> Optional[ListNode]:
s = set(nums)
pre = dummy = ListNode(next=head)
while pre.next:
if pre.next.val in s:
pre.next = pre.next.next
else:
pre = pre.next
return dummy.nextC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
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) {}
};
/**
* Definition for singly-linked list.
* 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* modifiedList(vector<int>& nums, ListNode* head) {
unordered_set<int> s(nums.begin(), nums.end());
ListNode* dummy = new ListNode(0, head);
for (ListNode* pre = dummy; pre->next;) {
if (s.count(pre->next->val)) {
pre->next = pre->next->next;
} else {
pre = pre->next;
}
}
return dummy->next;
}
};Java
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
Set<Integer> s = new HashSet<>();
for (int x : nums) {
s.add(x);
}
ListNode dummy = new ListNode(0, head);
for (ListNode pre = dummy; pre.next != null;) {
if (s.contains(pre.next.val)) {
pre.next = pre.next.next;
} else {
pre = pre.next;
}
}
return dummy.next;
}
}复杂度
时间
O(n + m)
m 是 nums 的长度,n 是链表节点数。建哈希集合把 m 个数放进去是 O(m);之后前驱指针从头到尾把链表走一遍,每个节点只被查一次集合、做一次常数操作,是 O(n)。两段相加就是 O(n + m)
空间
O(m)
按峰值算。额外开销主要是那个哈希集合,里面装了 nums 的 m 个值,占 O(m);哨兵和几个指针都是常数。整个过程在原链表上原地改指针,不另开一条新链,所以空间就是 O(m)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 从链表中移除在数组中存在的节点 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的整体思路是什么?+
先把 nums 装进哈希集合,让判断一个值在不在里面变成常数时间。再在头节点前接一个哨兵,用前驱指针 prev 从哨兵出发,反复看 prev.next:值在集合里就让 prev.next 越过它、把它摘掉,prev 不动;不在就让 prev 前进一格。走到 prev.next 为空结束,返回哨兵的 next。整趟只扫一遍链表。
哨兵节点解决了什么问题,不用行不行?+
哨兵解决的是删头节点的特殊情况。删一个节点靠的是它的前驱把指针接过去,而头节点没有前驱。不接哨兵就得为删头单写一段判断,还要在删头后更新 head。接一个哨兵挂在头前面,头节点也有了前驱,所有删除都统一成 prev.next 越过,最后返回 dummy.next 即可。不用哨兵也能做,但代码会多一段特判、更容易出错。
复杂度是多少,瓶颈在哪?+
设链表长 n、nums 长 m。建集合 O(m),扫链表每个节点常数操作 O(n),时间是 O(n 加 m)。空间的主要开销是那个哈希集合 O(m),链表是原地改指针不额外开链。如果不用集合、每次在 nums 里线性找,时间会退化成 O(n 乘 m),这也是最常见的优化点。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 从链表中移除在数组中存在的节点 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。