Sponsored
Sponsored
This approach uses a set for fast lookup of values that need to be removed from the linked list. By iterating through the linked list and checking if each node's value is in the set, we can efficiently determine which nodes to skip and which to keep.
Time Complexity: O(N + M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(M), where M is the size of nums.
1#include <unordered_set>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10ListNode* deleteNodes(ListNode* head, vector<int>& nums) {
11 unordered_set<int> s(nums.begin(), nums.end());
12 ListNode* dummy = new ListNode(0);
13 dummy->next = head;
14 ListNode* prev = dummy;
15 ListNode* current = head;
16
17 while (current) {
18 if (s.count(current->val)) {
19 prev->next = current->next;
20 } else {
21 prev = current;
22 }
23 current = current->next;
24 }
25 return dummy->next;
26}The C++ implementation uses an unordered_set for fast lookups. A dummy node assists in managing the previous node reference. We iterate through the linked list and adjust pointers based on the presence of node values in the set.
This approach leverages a two-pointer technique where the result is constructed in-place. Although it doesn't require extra storage for the set, it does involve modifications that make subsequent operations more complex in favor of reducing space usage.
Time Complexity: O(N * M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(1).
The C solution avoids extra space by implementing a linear search function isInArray that checks for value presence within the nums array, although less efficient than using a set for larger inputs.