diff options
Diffstat (limited to 'delete_node_link_list_arr.c')
-rw-r--r-- | delete_node_link_list_arr.c | 100 |
1 files changed, 100 insertions, 0 deletions
diff --git a/delete_node_link_list_arr.c b/delete_node_link_list_arr.c new file mode 100644 index 0000000..9237499 --- /dev/null +++ b/delete_node_link_list_arr.c @@ -0,0 +1,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); +} |