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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5struct ListNode {
6 int val;
7 struct ListNode *next;
8};
9
10struct ListNode* deleteNodes(struct ListNode* head, int* nums, int numsSize) {
11 bool lookup[100001] = { false };
12 for (int i = 0; i < numsSize; ++i) {
13 lookup[nums[i]] = true;
14 }
15 struct ListNode *dummy = malloc(sizeof(struct ListNode));
16 dummy->next = head;
17 struct ListNode *prev = dummy;
18 struct ListNode *current = head;
19
20 while (current != NULL) {
21 if (lookup[current->val]) {
22 prev->next = current->next;
23 } else {
24 prev = current;
25 }
26 current = current->next;
27 }
28 struct ListNode *newHead = dummy->next;
29 free(dummy);
30 return newHead;
31}The solution initializes a boolean array lookup to quickly check if a node value should be removed. As we traverse the list, we either skip or keep nodes based on the contents of lookup. A dummy node simplifies edge cases, like removing the list's head.
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).
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.