aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-05 18:31:51 -0600
committerJack Sangdahl <[email protected]>2024-09-05 18:31:51 -0600
commita8cd949394a582f8c8c4717b6def6f5041f921be (patch)
tree1051626df304029b8274cb2582331eeea06316cd
parent3efddf99809e035d7985b1d0838721d7a6d6b24d (diff)
downloadleetcode-a8cd949394a582f8c8c4717b6def6f5041f921be.tar.gz
leetcode-a8cd949394a582f8c8c4717b6def6f5041f921be.zip
3217. delete nodes from linked list present in array
-rw-r--r--delete_node_link_list_arr.c100
-rw-r--r--delete_node_link_list_arr.py40
2 files changed, 140 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);
+}
diff --git a/delete_node_link_list_arr.py b/delete_node_link_list_arr.py
new file mode 100644
index 0000000..78b33e6
--- /dev/null
+++ b/delete_node_link_list_arr.py
@@ -0,0 +1,40 @@
+# 3217. Delete Nodes From Linked List Present in Array
+
+"""
+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'.
+"""
+
+
+# Definition for singly-linked list.
+class ListNode(object):
+ def __init__(self, val=0, next=None):
+ self.val = val
+ self.next = next
+
+
+class Solution(object):
+ def modifiedList(self, nums, head):
+ """
+ :type nums: List[int]
+ :type head: Optional[ListNode]
+ :rtype: Optional[ListNode]
+ """
+ nums = set(nums)
+ while head.val in nums:
+ head = head.next
+ ans = ListNode(head.val, head)
+ while head and head.next:
+ if head.next.val in nums:
+ head.next = head.next.next
+ else:
+ head = head.next
+ return ans.next
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.modifiedList(nums=[1, 2, 3], head=[1, 2, 3, 4, 5]))
+ print(obj.modifiedList(nums=[1], head=[1, 2, 1, 2, 1, 2]))
+ print(obj.modifiedList(nums=[5], head=[1, 2, 3, 4]))