Beats 100% | Easy Code
\n# Intuition\nThe task involves modifying a linked list by removing nodes that contain certain values. The list of values to be removed is provided in a vector
![image.png](https://assets.leetcode.com/users/images/22c0bdd9-48e1-423d-89e8-767ff855f0b2_1725599724.476679.png)\n# Intuition\nThe task involves modifying a linked list by removing nodes that contain certain values. The list of values to be removed is provided in a vector nums. The solution leverages a bitset to efficiently store and look up these values. The goal is to traverse the linked list and remove nodes whose values are present in the bitset, without affecting the structure of the remaining nodes.\n\n# Approach\n1. Using a bitset for Fast Lookup:\n\n    - The idea is to use a bitset to store the values present in the nums array. This allows for fast constant-time lookups (O(1) complexity) when checking if a node\'s value should be removed from the linked list.\n2. Dummy Node:\n\n    - A dummy node (ListNode(-1)) is added at the beginning of the list. This simplifies edge cases, such as removing the head of the list, by ensuring that every node has a previous node to reference.\n3. Linked List Traversal:\n\n    - Start from the dummy node and traverse the list. For each node, check if its value is in the bitset. If it is, bypass the node by updating the next pointer of the previous node to skip the current node. Otherwise, move to the next node.\n4. Return the Modified List:\n\n    - After the traversal, return the list starting from dummy->next, which points to the real head of the modified list.\n# Complexity\n- Time Complexity:\n    - Constructing the bitset takes O(|nums|) where |nums| is the length of the nums vector.\n    - Traversing the linked list takes O(|list|), where |list| is the length of the linked list.\n    - Therefore, the overall time complexity is O(|nums| + |list|).\n- Space Complexity:\n    - The bitset uses constant space (O(100001)), which is efficient given that it only holds boolean values for a fixed range.\n    - The space complexity is O(1) apart from the input and output space (linked list and bitset).\n# Code\n```cpp []\nclass Solution {\npublic:\n    ListNode* modifiedList(vector<int>& nums, ListNode* head) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n\n        bitset<100001> bs;\n        for(const int & i : nums){\n            bs.set(i);\n        }\n        \n        head = new ListNode(-1,head);\n        ListNode * prev = head;\n        while(head->next){\n            if(bs[head->next->val]){\n                head->next = head->next->next;\n            }else{\n                head = head->next;\n            }\n        }\n        return prev->next;\n    }\n};\n```\n```Java []\nclass Solution {\n    public ListNode modifiedList(int[] nums, ListNode head) {\n        BitSet bs = new BitSet(100001);\n        for (int num : nums) {\n            bs.set(num);\n        }\n\n        ListNode dummy = new ListNode(-1, head);\n        ListNode prev = dummy;\n\n        while (head != null) {\n            if (bs.get(head.val)) {\n                prev.next = head.next;\n            } else {\n                prev = head;\n            }\n            head = head.next;\n        }\n        \n        return dummy.next;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def modifiedList(self, nums, head):\n        bs = [False] * 100001\n        for num in nums:\n            bs[num] = True\n\n        dummy = ListNode(-1, head)\n        prev = dummy\n\n        while head:\n            if bs[head.val]:\n                prev.next = head.next\n            else:\n                prev = head\n            head = head.next\n\n        return dummy.next\n\n```\n```Javascript []\nvar modifiedList = function(nums, head) {\n    let bs = new Array(100001).fill(false);\n    for (let num of nums) {\n        bs[num] = true;\n    }\n\n    let dummy = new ListNode(-1, head);\n    let prev = dummy;\n\n    while (head) {\n        if (bs[head.val]) {\n            prev.next = head.next;\n        } else {\n            prev = head;\n        }\n        head = head.next;\n    }\n\n    return dummy.next;\n};\n\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/2e0244ee-c459-49a5-8987-bb1225795ad9_1725599797.2296314.png)\n
['Array', 'Hash Table', 'Linked List', 'Python', 'C++', 'Java', 'JavaScript']