aboutsummaryrefslogtreecommitdiff
path: root/delete_node_link_list_arr.c
diff options
context:
space:
mode:
Diffstat (limited to 'delete_node_link_list_arr.c')
-rw-r--r--delete_node_link_list_arr.c100
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);
+}