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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
// 3217. Delete Nodes From Linked List Present in Array
#include "leetcode.h"
/*
* you are given an array of integers 'nums' and the 'head' of a linked list.
* return the 'head' of the modified linked list after removing all nodes from
* the linked list that have a value that exists in 'nums'.
*/
#define HASH_SIZE 1000
struct hash_node {
int val;
struct hash_node *next;
};
int find_idx(int val) { return val % HASH_SIZE; }
void insert_hash_table(struct hash_node **table, int val) {
int hash_idx = find_idx(val);
if (!table[hash_idx]) {
struct hash_node *new_hash =
(struct hash_node *)malloc(sizeof(struct hash_node));
new_hash->val = val;
new_hash->next = NULL;
table[hash_idx] = new_hash;
return;
}
struct hash_node *trav = table[hash_idx], *prev = NULL;
while (trav) {
if (trav->val == val)
return;
else if (val > trav->val) {
prev = trav;
trav = trav->next;
} else
break;
}
struct hash_node *new_hash =
(struct hash_node *)malloc(sizeof(struct hash_node));
new_hash->val = val;
if (!prev) {
table[hash_idx] = new_hash;
new_hash->next = trav;
} else {
prev->next = new_hash;
new_hash->next = trav;
}
return;
}
bool search_hash_table(struct hash_node **table, int val) {
int hash_idx = find_idx(val);
struct hash_node *trav = table[hash_idx];
while (trav) {
if (trav->val)
return true;
trav = trav->next;
}
return false;
}
struct ListNode *modifiedList(int *nums, int numsSize, struct ListNode *head) {
struct hash_node **table =
(struct hash_node **)malloc(sizeof(struct hash_node *) * HASH_SIZE);
for (int i = 0; i < HASH_SIZE; i++)
table[i] = NULL;
for (int i = 0; i < numsSize; i++)
insert_hash_table(table, nums[i]);
struct ListNode *prev = NULL, *trav = head;
while (trav) {
bool found = search_hash_table(table, trav->val);
if (found) {
struct ListNode *del_node = trav;
trav = trav->next;
if (prev)
prev->next = trav;
else
head = trav;
free(del_node);
} else {
prev = trav;
trav = trav->next;
}
}
return head;
}
int main() {
int nums[] = {1, 2, 3};
struct ListNode *head = listnode_create(1);
head->next = listnode_create(2);
head->next->next = listnode_create(3);
head->next->next->next = listnode_create(4);
head->next->next->next->next = listnode_create(5);
struct ListNode *ml1 = modifiedList(nums, ARRAY_SIZE(nums), head);
listnode_print(ml1); // expect: 4 5
listnode_free(head);
listnode_free(ml1);
}
|