时间轴

2025-11-01

init

题目：

P3217 从链表中移除在数组中存在的节点

https://leetcode.cn/problems/delete-nodes-from-linked-list-present-in-array/description/?envType=daily-question&envId=2025-11-01

用哈希表来查找要删除的元素，将时间复杂度降低到O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <climits>
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)
	{
	}
};

#include <vector>
#include <unordered_set>

using std::vector;
using std::unordered_set;

class Solution {
    public:
	ListNode *modifiedList(vector<int> &nums, ListNode *head)
	{
		int i, n;
		ListNode dummy;
		dummy.next = head;
		dummy.val = INT_MAX;
		ListNode *p = &dummy;

		n = nums.size();

		unordered_set<int> uset;
		ListNode *tmp;

		for (i = 0; i < n; i++) {
			uset.insert(nums[i]);
		}

		while (p->next) {
			if (uset.count(p->next->val) != 0) {
				tmp = p->next;
				p->next = tmp->next;
				delete tmp;
			}else{
			    p = p->next;
			}
		}
		return dummy.next;
	}
};

#include <iostream>
using std::cout;
using std::endl;

int main() {
	vector<int> nums = {1, 2, 3};
	ListNode *head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

	Solution s;
	ListNode *res = s.modifiedList(nums, head);

	// 输出结果
	while (res) {
		cout << res->val;
		if (res->next) cout << " -> ";
		res = res->next;
	}
	cout << endl;

	return 0;
}