Delete Nodes From Linked List Present In Array || DCC 06/09/24 || Beginner Friendly Solution🔥🔥
Intuition\nThe problem requires modifying a linked list by removing nodes whose values exist in a given array nums. The idea is to traverse through the linked l
# Intuition\nThe problem requires modifying a linked list by removing nodes whose values exist in a given array `nums`. The idea is to traverse through the linked list and remove any node whose value is present in the nums array.\n\n# Approach\n**Convert nums to a Set:**\n- You use a `set` to store all the values from the array `nums`. This allows for $$O(1)$$ average-time complexity checks when determining if a value should be removed from the linked list.\n\n**Traverse and Mark Nodes:**\n- You traverse the linked list and mark nodes for removal by setting their value to $$0$$. This is done to avoid altering the linked list structure during the initial traversal.\n\n**Remove Marked Nodes:**\n- You traverse the linked list again, this time removing nodes that were marked with the value 0. \n- You handle three cases:\n->If the node to be removed is the head, adjust the head pointer.\n->If the node to be removed is in the middle or end, adjust pointers to skip over the removed node.\n->Ensure that all nodes are correctly removed, and the list is properly updated.\n\n# Complexity\n**Time complexity:**\n- Conversion to Set: $$O(N)$$ where N is the number of elements in nums. This is because each insertion into the set takes $$O(1)$$ on average.\n- First Traversal of Linked List: $$O(L)$$ where L is the number of nodes in the linked list. Each node is checked once.\n- Second Traversal and Removal: $$O(L)$$ for traversing the list again and removing nodes.\n- Therefore, the total time complexity is $$O(N + L)$$, where N is the size of nums and L is the size of the linked list.\n\n**Space complexity:**\n- Space for Set: $$O(N)$$, where N is the number of unique values in nums.\n- Space for Linked List Nodes: $$O(L)$$, but this is part of the input and not extra space used.\n- Thus, the space complexity is $$O(N)$$ for the additional space used by the set.\n\n# Code\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        int i=0;\n        set<long long int> st;\n\n        for(int i=0; i<nums.size(); i++){\n            st.insert(nums[i]);\n        }\n\n        \n            ListNode* temp=head;\n\n            while(temp!=NULL){\n              if(temp!=NULL && st.find(temp->val)!=st.end()){\n                temp->val=0;\n              }\n                temp=temp->next;\n            }\n            \n              \n            \n\n            ListNode* prevN= NULL;\n            ListNode* currN= head;\n\n            while(currN){\n\n                while(currN!=NULL && currN->val!=0){\n                    prevN=currN;\n                    currN=currN->next;\n                }\n                if(prevN==NULL && currN->val==0){\n                    head= currN->next;\n                    currN->next= NULL;\n                    currN= head;\n                }\n                \n                else if(prevN->next!=NULL && currN->val==0){\n                    ListNode* nextN= currN->next;\n                    prevN->next= nextN;\n                    currN->next= NULL;\n                    currN=nextN;\n                  }\n                else{\n                    return head;\n                }\n            }\n            return head;\n    }\n};\n```
['Array', 'Linked List', 'Ordered Set', 'C++']