Python | Two Pointers & Dummy Node
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Option
[see the Successfully Accepted Submission](https://leetcode.com/problems/delete-nodes-from-linked-list-present-in-array/submissions/1380783070/?envType=daily-question&envId=2024-09-06)\n\n# Code\n```python3 []\nclass Solution:\n    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:\n        # Convert nums to a set for O(1) lookup\n        num_set = set(nums)\n        \n        # Create a dummy node to handle edge cases where the head itself needs to be removed\n        dummy = ListNode(0)\n        dummy.next = head\n        \n        # Corrected: Two pointers - prev starts at dummy, and current starts at head\n        prev, current = dummy, head\n        \n        while current:\n            if current.val in num_set:\n                # Skip the current node by linking prev to current.next\n                prev.next = current.next\n            else:\n                # Move prev to current if current is not removed\n                prev = current\n            # Move to the next node in the list\n            current = current.next\n        \n        # Return the new head (which is dummy.next)\n        return dummy.next\n\n```\n\n## Approach:\n\n1. **Convert `nums` to a set**: \n   Since checking for an element in a set is O(1) compared to O(n) in a list, we first convert the `nums` array into a set. This will allow us to efficiently check whether the value of a node in the linked list exists in `nums`.\n\n2. **Traverse the linked list**: \n   We\'ll traverse through the linked list and skip the nodes that have a value found in the `nums` set.\n\n3. **Maintain a dummy node**: \n   To simplify the edge cases (like when the head node itself needs to be removed), we\'ll use a dummy node that points to the head of the linked list. This will help in re-assigning the head if the first few nodes are removed.\n\n4. **Two-pointer approach**:\n   - One pointer (`current`) will traverse through the list.\n   - Another pointer (`prev`) will keep track of the last valid node (i.e., a node whose value is not in `nums`).\n   - When we encounter a node whose value is in `nums`, we\'ll bypass that node by setting `prev.next = current.next`.\n\n5. **Return the modified list**: \n   After traversing the list, we return the list starting from `dummy.next` which will skip any removed nodes at the beginning of the list.\n\n---\n\n## Explanation:\n\n1. **`num_set = set(nums)`**: \n   We convert the `nums` list into a set to improve the lookup time.\n\n2. **`dummy = ListNode(0)`**: \n   We create a dummy node that points to the head. This helps in simplifying the logic when the head needs to be removed, as we can always return `dummy.next`.\n\n3. **`prev, current = dummy, head`**:\n   - `prev` keeps track of the last valid node (the one before the nodes that will be removed).\n   - `current` is the node being checked.\n\n4. **`if current.val in num_set`**: \n   If the value of the `current` node is in `nums`, we skip this node by setting `prev.next = current.next`.\n\n5. **`prev = current`**: \n   If the node is not removed, we move `prev` to point to `current`.\n\n6. **`current = current.next`**: \n   Move the `current` pointer to the next node in the list.\n\n7. **Return `dummy.next`**: \n   The modified list is returned, skipping the nodes removed at the beginning.\n\n---\n\n## Time Complexity:\n\n- The time complexity is O(n), where `n` is the number of nodes in the linked list. This is because we traverse the linked list once.\n- Converting `nums` into a set is O(m), where `m` is the length of `nums`.\n\nThus, the overall time complexity is O(n + m).\n\n---\n\n## Example:\n\nFor `nums = [1, 2, 3]` and `head = [1, 2, 3, 4, 5]`, the output will be `[4, 5]` because nodes with values 1, 2, and 3 will be removed.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']