Linked List+bitset without Memory leaks||343 ms Beats 99.05%
Intuition\n Describe your first thoughts on how to solve this problem. \nRemove the nodes with values seen in nums.\nUse a bitset to record the nums; then trans
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nRemove the nodes with values seen in `nums`.\nUse a bitset to record the nums; then transverse the linked list `head` to proceed.\n\nFor comparison, an unordered_set version is also implemented.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use `bitset<100001> hasN=0` to set `x in nums` to be `hasN[x]=1` instead of using `unordered_set`.\n2. Declare a dummy node `ListNode dummy(0, head)`.\n3. Initialize `prev=&dummy, *tmp=NULL`\n4. Use a loop to proceed `for(ListNode* curr=head; curr; curr=curr->next, delete tmp){....}` which deletes the node removed to avoid of memory leakage.\n5. The iteration in the loop is:\n```\nif (hasN[curr->val]){ \n    prev->next = curr->next;\n    tmp=curr;\n}\nelse{\n    prev = prev->next;\n    tmp=NULL;\n}\n```\n6. ` dummy.next` is the answer.\n7. 2nd C++ using unordered_set is also made.\n\n|Method|Elapsed time|Record|Memory|\n|---|---|---|---|\n|bitset w/o Memory leaks|343ms|99.05%|227.92MB|\n|bitset with Memory leaks|346ms|98.94%|223.56MB|\n|unordered_set w/o Memory leaks|454ms|47.11%|262.89MB|\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(|nums|+|head|)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(10^5)$\n# Code||343 ms Beats 99.05%\n```cpp []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* modifiedList(vector<int>& nums, ListNode* head) {\n        bitset<100001> hasN=0;\n        for(int x: nums) hasN[x]=1;\n        ListNode dummy(0, head);\n        ListNode* prev=&dummy, *tmp=NULL;\n        for(ListNode* curr=head; curr; curr=curr->next, delete tmp){\n            if (hasN[curr->val]){ \n                prev->next = curr->next;\n                tmp=curr;\n            }\n            else{\n                prev = prev->next;\n                tmp=NULL;\n            }\n        }\n        return dummy.next;\n    }\n};\n```\n# C++ with unordered_set||454ms Beats 47.11%\n```\nclass Solution {\npublic:\n    ListNode* modifiedList(vector<int>& nums, ListNode* head) {\n        unordered_set<int> hasN(nums.begin(), nums.end());\n        ListNode dummy(0, head);\n        ListNode* prev=&dummy, *tmp=NULL;\n        for(ListNode* curr=head; curr; curr=curr->next, delete tmp){\n            if (hasN.count(curr->val)){ \n                prev->next = curr->next;\n                tmp=curr;\n            }\n            else{\n                prev = prev->next;\n                tmp=NULL;\n            }\n        }\n        return dummy.next;\n    }\n};\n```\nClassical Leetcode question [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/solutions/4813267/fast-slow-pointers-care-with-memory-leaks-0ms-beats-100/)\n[Please turn on English subtitles if necessary]\n[https://youtu.be/OqLR3ShDALY?si=SDv3JLDQxgsfJGNf](https://youtu.be/OqLR3ShDALY?si=SDv3JLDQxgsfJGNf)
['Hash Table', 'Linked List', 'Bit Manipulation', 'C++']