commit ebc69b929dabb079751897ecabca77f2f940e4ec
parent b05b821f2432ed8d1a770a9c96abf9726c3d30fe
Author: Jack Sangdahl <jack@pngu.org>
Date: Fri, 31 Oct 2025 21:11:35 -0600
3217. delete nodes from linked list present in array
Diffstat:
2 files changed, 44 insertions(+), 100 deletions(-)
diff --git a/delete_node_link_list_arr.c b/delete_node_link_list_arr.c
@@ -7,94 +7,40 @@
* 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;
+ bool map[100001] = {false};
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;
- }
+ if (nums[i] >= 0 && nums[i] <= 100000)
+ map[nums[i]] = true;
+ while (head && map[head->val])
+ head = head->next;
+ struct ListNode *curr = head;
+ while (curr && curr->next) {
+ if (map[curr->next->val])
+ curr->next = curr->next->next;
+ else
+ curr = curr->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);
+ int n1[] = {1, 2, 3}, h1i[] = {1, 2, 3, 4, 5};
+ int n2[] = {1}, h2i[] = {1, 2, 1, 2, 1, 2};
+ int n3[] = {5}, h3i[] = {1, 2, 3, 4};
+ struct ListNode *h1 = listnode_build(h1i, ARRAY_SIZE(h1i));
+ struct ListNode *h2 = listnode_build(h1i, ARRAY_SIZE(h1i));
+ struct ListNode *h3 = listnode_build(h1i, ARRAY_SIZE(h1i));
+ struct ListNode *ml1 = modifiedList(n1, ARRAY_SIZE(n1), h1);
+ struct ListNode *ml2 = modifiedList(n2, ARRAY_SIZE(n2), h2);
+ struct ListNode *ml3 = modifiedList(n3, ARRAY_SIZE(n3), h3);
listnode_print(ml1); // expect: 4 5
- listnode_free(head);
+ listnode_print(ml2); // expect: 2 2 2
+ listnode_print(ml3); // expect: 1 2 3 4
+ listnode_free(h1);
+ listnode_free(h2);
+ listnode_free(h3);
listnode_free(ml1);
+ listnode_free(ml2);
+ listnode_free(ml3);
}
diff --git a/delete_node_link_list_arr.py b/delete_node_link_list_arr.py
@@ -1,4 +1,5 @@
# 3217. Delete Nodes From Linked List Present in Array
+from leetcode import ListNode, listnode_build
"""
you are given an array of integers 'nums' and the 'head' of a linked list.
@@ -7,13 +8,6 @@ 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):
"""
@@ -21,20 +15,24 @@ class Solution(object):
: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
+ map = set(nums)
+ tmp = ListNode(0, head)
+ prev, curr = tmp, head
+ curr = head
+ while curr:
+ if curr.val in map:
+ prev.next = curr.next
else:
- head = head.next
- return ans.next
+ prev = prev.next
+ curr = curr.next
+ return tmp.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]))
+ n1, h1 = [1, 2, 3], listnode_build(vals=[1, 2, 3, 4, 5])
+ n2, h2 = [1], listnode_build(vals=[1, 2, 1, 2, 1, 2])
+ n3, h3 = [5], listnode_build(vals=[1, 2, 3, 4])
+ print(obj.modifiedList(n1, h1))
+ print(obj.modifiedList(n2, h2))
+ print(obj.modifiedList(n3, h3))
