2 approaches Explained | CPP 🔥 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n1. Creating a Set fro
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. **Creating a Set from the Vector**:\n   ```cpp\n   unordered_set<int> s(nums.begin(), nums.end());\n   ```\n   The elements of `nums` are stored in an unordered set `s` for fast lookup. This allows checking if a node\'s value is in `nums` in constant time on average.\n\n2. **Dummy Node**:\n   ```cpp\n   ListNode* dummy = new ListNode(0);\n   dummy->next = head;\n   ```\n   A dummy node is created with value `0` and its `next` pointer set to the head of the linked list. This dummy node helps to simplify handling the case when the head of the list itself needs to be removed.\n\n3. **Two Pointers: `prev` and `curr`**:\n   ```cpp\n   ListNode* prev = dummy;\n   ListNode* curr = head;\n   ```\n   Two pointers, `prev` and `curr`, are initialized. `prev` is used to keep track of the last node that remains in the list, and `curr` is used to traverse the list.\n\n4. **Traversing the List and Removing Nodes**:\n   ```cpp\n   while (curr != nullptr) {\n       if (s.find(curr->val) != s.end()) {\n           prev->next = curr->next;\n       } else {\n           prev = curr;\n       }\n       curr = curr->next;\n   }\n   ```\n   The list is traversed using `curr`. For each node:\n   - If the value of `curr` is found in the set `s`, that node is removed by setting `prev->next` to `curr->next` (skipping the current node).\n   - If the value is not in the set, both `prev` and `curr` move forward.\n   - `curr` is always moved to the next node in each iteration.\n\n5. **Returning the Modified List**:\n   ```cpp\n   return dummy->next;\n   ```\n   After the loop, the modified list is returned starting from `dummy->next`, which points to the new head (or the original head if no nodes were removed).\n\n---\n\n# Complexity\n- Time complexity:O(n+m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code 1\n```cpp []\nclass Solution {\npublic:\n    ListNode* modifiedList(vector<int>& nums, ListNode* head) {\n        // Step 1: Store the elements from the vector in a set for fast lookup.\n        unordered_set<int> s(nums.begin(), nums.end());\n\n        ListNode* dummy = new ListNode(0);\n        dummy->next = head;\n\n        ListNode* prev = dummy;\n        ListNode* curr = head;\n\n        while (curr != nullptr) {\n            if (s.find(curr->val) != s.end()) {\n                prev->next = curr->next;\n            } else {\n                prev = curr;\n            }\n            curr = curr->next;\n        }\n\n        return dummy->next;\n    }\n};\n\n```\n\n# Code 2 explanation \n\n\n1. **Creating an Unordered Set from the Vector**:\n   ```cpp\n   unordered_set<int>s;\n   for(int i = 0; i < nums.size(); i++) {\n       s.insert(nums[i]);\n   }\n   ```\n   A set `s` is created to store all the elements of `nums`. This helps to quickly check whether a value exists in `nums`, as lookups in an unordered set take average constant time (**O(1)**).\n\n2. **Traversing the Original Linked List**:\n   ```cpp\n   ListNode* temp = head;\n   ListNode* curr = new ListNode(0);\n   vector<int> ans;\n   while(temp != NULL) {\n       int val1 = temp->val;\n       if(s.find(val1) == s.end()) {\n           ans.push_back(val1);\n       }\n       temp = temp->next;\n   }\n   ```\n   - The linked list is traversed using the `temp` pointer. For each node:\n     - The value `val1` of the current node (`temp->val`) is checked against the set `s`.\n     - If the value is **not** found in the set (`s.find(val1) == s.end()`), it is pushed into the vector `ans`.\n   - After processing all nodes, `ans` contains the values from the original list that are **not** in the vector `nums`.\n\n3. **Creating a New Linked List**:\n   ```cpp\n   ListNode* anshead = new ListNode(0);\n   ListNode* tail = anshead;\n   for(int i = 0; i < ans.size(); i++) {\n       ListNode* temp = new ListNode(ans[i]);\n       tail->next = temp;\n       tail = temp;\n   }\n   return anshead->next;\n   ```\n   - A new linked list is constructed using the values stored in the `ans` vector. \n   - A dummy node (`anshead`) is used to simplify building the new list.\n   - The new nodes are created with values from `ans`, and linked using the `tail` pointer.\n   - Finally, the function returns `anshead->next`, which points to the head of the new linked list (skipping the dummy node).\n\n# Complexity\n- Time complexity:O(n+m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n+m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code 2\n```cpp []\nclass Solution {\npublic:\n    ListNode* modifiedList(vector<int>& nums, ListNode* head) {\n        unordered_set<int>s;\n        for(int i =0;i<nums.size();i++)\n        {\n            s.insert(nums[i]);\n        }\n\n        ListNode* temp = head;\n        ListNode* curr = new ListNode(0);\n        vector<int>ans;\n        while(temp!=NULL)\n        {\n            int val1 = temp->val;\n            if(s.find(val1)==s.end())\n            {\n                ans.push_back(val1);\n                \n            }\n            temp = temp->next;\n            \n        }\n\n        ListNode* anshead = new ListNode(0);\n        ListNode* tail = anshead;\n        for(int i=0;i<ans.size();i++)\n        {\n            ListNode* temp = new ListNode(ans[i]);\n            tail->next = temp;\n            tail = temp;\n        }\n        return anshead->next;\n        \n    }\n};\n\n```\n\n\n
['Array', 'Linked List', 'C++']