题目描述
给你一个整数数组 nums
和一个链表的头节点 head
。从链表中移除所有存在于 nums
中的节点后,返回修改后的链表的头节点。
样例
输入: nums = [1,2,3], head = [1,2,3,4,5]
输出: [4,5]
解释:
移除数值为 1, 2 和 3 的节点。
输入: nums = [1], head = [1,2,1,2,1,2]
输出: [2,2,2]
解释:
移除数值为 1 的节点。
输入: nums = [5], head = [1,2,3,4]
输出: [1,2,3,4]
解释:
链表中不存在值为 5 的节点。
限制
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
nums
中的所有元素都是唯一的。- 链表中的节点数在
[1, 10^5]
的范围内。 1 <= Node.val <= 10^5
- 输入保证链表中至少有一个值没有在
nums
中出现过。
算法
(哈希表) $O(n + m)$
- 将数组存储到哈希表中,然后遍历链表。
- 增加一个
dummy
节点,指向原表头。 - 遍历时,如果下一个节点出现在了哈希表中,则将当前节点的
next
指针指向下下个节点。 - 否则,按照
next
指针移动到下一个节点。
时间复杂度
- 构造哈希表的时间复杂度为 $O(n)$。
- 遍历链表的时间复杂度为 $O(m)$。
- 故总时间复杂度为 $O(n + m)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
/**
* 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> h(nums.begin(), nums.end());
ListNode *dummy = new ListNode(0, head);
ListNode *p = dummy;
while (p->next) {
if (h.find(p->next->val) != h.end())
p->next = p->next->next;
else
p = p->next;
}
return dummy->next;
}
};