题目描述
思路解析动画文字版
记牢这套动作:prev 盯着自己的下一个节点,命中集合就断链跳过、prev 原地不动;没命中才让 prev 前进一格。哨兵的作用是让删头节点也走这同一套逻辑。下面从哨兵开始扫。
原链表 · 待处理 3 1 5 2 7 4：先把这条链表看清楚。从左到右 6 个节点,值依次是 3、1、5、2、7、4。最左边那个写着 D 的方块是我等下要接上的哨兵,先别管它。任务是把值等于 3、5、7 的节点全删掉。
第一步 · 把 nums 装进哈希集合：第一步,把 nums 里的 3、5、7 全塞进一个哈希集合 s。为什么不直接在 nums 里一个个找?因为那样每查一次都要扫一遍 nums,太慢。装进集合后,问一个值在不在里面,基本是一瞬间的事。
第二步 · 哨兵 D 接在表头前,prev 站上哨兵：第二步,在真正的头节点 3 前面接一个哨兵 D,再让前驱指针 prev 站在 D 上。有了哨兵,哪怕头节点要删,也能靠 prev 从前面把它跳过去,不用为删头单独写一套代码。现在 prev 的下一个,正是链表第一个节点 3。
开扫 · prev 在哨兵,先看它的下一个：一切就位。集合建好了,哨兵接上了,prev 站在哨兵上。接下来就重复一个动作:只要 prev 后面还有节点,就拿它的值去问集合。我们从 prev 的下一个,也就是节点 3,开始。
看 prev 的下一个 · 节点 3 在集合里吗：prev 现在停在 哨兵 D,它的下一个节点值是 3。拿这个 3 去问集合 {3, 5, 7}:你在不在里面?在,这个节点得删。
命中 · 断链跳过节点 3：3 确实在集合里,那就把它摘掉:让 哨兵 D 的指针越过 3,直接接到它后面那个节点。3 就此从链上掉队,变灰。注意 prev 这时候一步都不能挪,因为新接上来的节点还没查过,得原地接着看它。
断链后 · prev 后面接上了 1：摘除完成。现在 哨兵 D 后面接上的是 1,prev 依旧停在原地。目前为止删掉的是 3。下一轮就轮到查这个新接上来的 1 了。
看 prev 的下一个 · 节点 1 在集合里吗：prev 现在停在 哨兵 D,它的下一个节点值是 1。拿这个 1 去问集合 {3, 5, 7}:你在不在里面?不在,这个节点要留下。
保留 · prev 前进到节点 1：1 不在集合里,是要留下的节点,标成蓝色。这时候 prev 才往前走一格,踩到 1 上,准备去看它后面的节点。到目前为止保下来的是 1。
看 prev 的下一个 · 节点 5 在集合里吗：prev 现在停在 1,它的下一个节点值是 5。拿这个 5 去问集合 {3, 5, 7}:你在不在里面?在,这个节点得删。
命中 · 断链跳过节点 5：5 确实在集合里,那就把它摘掉:让 1 的指针越过 5,直接接到它后面那个节点。5 就此从链上掉队,变灰。注意 prev 这时候一步都不能挪,因为新接上来的节点还没查过,得原地接着看它。
断链后 · prev 后面接上了 2：摘除完成。现在 1 后面接上的是 2,prev 依旧停在原地。目前为止删掉的是 3、5。下一轮就轮到查这个新接上来的 2 了。
看 prev 的下一个 · 节点 2 在集合里吗：prev 现在停在 1,它的下一个节点值是 2。拿这个 2 去问集合 {3, 5, 7}:你在不在里面?不在,这个节点要留下。
保留 · prev 前进到节点 2：2 不在集合里,是要留下的节点,标成蓝色。这时候 prev 才往前走一格,踩到 2 上,准备去看它后面的节点。到目前为止保下来的是 1、2。
看 prev 的下一个 · 节点 7 在集合里吗：prev 现在停在 2,它的下一个节点值是 7。拿这个 7 去问集合 {3, 5, 7}:你在不在里面?在,这个节点得删。
命中 · 断链跳过节点 7：7 确实在集合里,那就把它摘掉:让 2 的指针越过 7,直接接到它后面那个节点。7 就此从链上掉队,变灰。注意 prev 这时候一步都不能挪,因为新接上来的节点还没查过,得原地接着看它。
断链后 · prev 后面接上了 4：摘除完成。现在 2 后面接上的是 4,prev 依旧停在原地。目前为止删掉的是 3、5、7。下一轮就轮到查这个新接上来的 4 了。
看 prev 的下一个 · 节点 4 在集合里吗：prev 现在停在 2,它的下一个节点值是 4。拿这个 4 去问集合 {3, 5, 7}:你在不在里面?不在,这个节点要留下。
保留 · prev 前进到节点 4：4 不在集合里,是要留下的节点,标成蓝色。这时候 prev 才往前走一格,踩到 4 上,准备去看它后面的节点。到目前为止保下来的是 1、2、4。
收工 · prev 后面没有节点了：prev 现在停在最后保留下来的节点 4,它后面已经没有节点了,prev.next 是空。这就是循环的终点。返回哨兵的下一个,也就是新链表真正的头。
回放 · 最终链表 1 2 4：回头看全程。灰掉的 3、5、7 是命中集合被摘掉的,蓝色的 1、2、4 是一路留下来的。把蓝色节点顺次连起来,就是最终链表 1、2、4。整趟只从头到尾走了一遍,靠哨兵和前驱指针把删头、删中间统一成同一套动作。
边界想清:没命中就全保留、重复值靠集合一个不漏地删、开头连续命中靠哨兵接连跳过。
面试重点:哈希集合加哨兵加前驱指针一趟扫、哨兵免去删头特判、时间 O(n 加 m) 空间 O(m)。
参考代码
from __future__ import annotationsfrom 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 = rightclass 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 = nextclass 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.next复杂度
- 时间：O(n + m)，m 是 nums 的长度,n 是链表节点数。建哈希集合把 m 个数放进去是 O(m);之后前驱指针从头到尾把链表走一遍,每个节点只被查一次集合、做一次常数操作,是 O(n)。两段相加就是 O(n + m)
- 空间：O(m)，按峰值算。额外开销主要是那个哈希集合,里面装了 nums 的 m 个值,占 O(m);哨兵和几个指针都是常数。整个过程在原链表上原地改指针,不另开一条新链,所以空间就是 O(m)
易错点
面试追问把动画讲成自己的话
追问这题的整体思路是什么?
追问哨兵节点解决了什么问题,不用行不行?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
K 个一组翻转链表
LeetCode 25 · 困难 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题