aboutsummaryrefslogtreecommitdiff
path: root/delete_node_link_list_arr.c
blob: 9237499b3f0558facfd6b87aedfeca2ac424684d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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);
}