diff options
author | Jack Sangdahl <[email protected]> | 2024-09-05 18:31:51 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-05 18:31:51 -0600 |
commit | a8cd949394a582f8c8c4717b6def6f5041f921be (patch) | |
tree | 1051626df304029b8274cb2582331eeea06316cd | |
parent | 3efddf99809e035d7985b1d0838721d7a6d6b24d (diff) | |
download | leetcode-a8cd949394a582f8c8c4717b6def6f5041f921be.tar.gz leetcode-a8cd949394a582f8c8c4717b6def6f5041f921be.zip |
3217. delete nodes from linked list present in array
-rw-r--r-- | delete_node_link_list_arr.c | 100 | ||||
-rw-r--r-- | delete_node_link_list_arr.py | 40 |
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])) |