LeetCode 题解工作台
从链表中移除在数组中存在的节点
给你一个整数数组 nums 和一个链表的头节点 head 。从链表中 移除 所有存在于 nums 中的节点后，返回修改后的链表的头节点。 示例 1： 输入： nums = [1,2,3], head = [1,2,3,4,5] 输出： [4,5] 解释： 移除数值为 1, 2 和 3 的节点。 示例…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以使用一个哈希表 来存储数组 中的所有元素，然后定义一个虚拟节点 ，将其指向链表的头节点 。 接下来，我们遍历从虚拟节点 开始的链表，如果当前节点的下一个节点的值在哈希表 中，我们就将当前节点的指针指向下下个节点，否则我们就将当前节点指针指向下一个节点。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。
示例 1：
输入： nums = [1,2,3], head = [1,2,3,4,5]
输出： [4,5]
解释：
移除数值为 1, 2 和 3 的节点。
示例 2：
输入： nums = [1], head = [1,2,1,2,1,2]
输出： [2,2,2]
解释：
移除数值为 1 的节点。
示例 3：
输入： nums = [5], head = [1,2,3,4]
输出： [1,2,3,4]
解释：
链表中不存在值为 5 的节点。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105nums中的所有元素都是唯一的。- 链表中的节点数在
[1, 105]的范围内。 1 <= Node.val <= 105- 输入保证链表中至少有一个值没有在
nums中出现过。
解题思路
方法一：哈希表
我们可以使用一个哈希表 来存储数组 中的所有元素，然后定义一个虚拟节点 ，将其指向链表的头节点 。
接下来，我们遍历从虚拟节点 开始的链表，如果当前节点的下一个节点的值在哈希表 中，我们就将当前节点的指针指向下下个节点，否则我们就将当前节点指针指向下一个节点。
最后，我们返回虚拟节点 的下一个节点。
时间复杂度 ，空间复杂度 。其中 为数组 的长度，而 为链表 的长度。
# 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.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m + n) |
| 空间 | O(m) |
面试官常问的追问
外企场景- question_mark
The candidate effectively uses a HashSet for O(1) lookups, indicating a solid understanding of hashing and time complexity trade-offs.
- question_mark
The solution demonstrates proficiency in traversing and modifying linked lists in-place, which is a common interview pattern.
- question_mark
The candidate handles edge cases well, ensuring the solution works for both empty lists and lists that require no deletions.
常见陷阱
外企场景- error
Not using a HashSet for quick lookups, which could lead to an inefficient solution with O(n) lookups for each node.
- error
Incorrect pointer manipulation while skipping nodes, which can break the linked list structure and lead to memory leaks or infinite loops.
- error
Failing to account for cases where no deletions are needed or when the list is empty.
进阶变体
外企场景- arrow_right_alt
The problem can be extended to delete nodes based on multiple arrays rather than a single one.
- arrow_right_alt
Instead of removing nodes in-place, the candidate could return a new linked list with the nodes that remain.
- arrow_right_alt
Another variant could involve sorting the linked list before deleting nodes, which may have additional time complexity considerations.