3217. Delete Nodes From Linked List Present in Array

You are given an array of integers nums and the head of a linked list. Return the head of the modified linked list after removing all nodes from the linked list that have a value that exists in nums.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• All elements in nums are unique.
• The number of nodes in the given list is in the range [1, 105].
• 1 <= Node.val <= 105
• The input is generated such that there is at least one node in the linked list that has a value not present in nums.

Approach 01:

#include <unordered_set>
#include <vector>

class Solution {
public:
    ListNode* modifiedList(const std::vector<int>& nums, ListNode* head) {
        // Create a dummy node to handle edge cases.
        ListNode* result = new ListNode(0, head);
        
        // Convert the vector into an unordered set for quick lookup.
        std::unordered_set<int> numSet(nums.begin(), nums.end());
        
        ListNode* currentNode = result;
        
        // Traverse the linked list.
        while (currentNode->next) {
            if (numSet.find(currentNode->next->val) != numSet.end()) {
                // If the next node's value is in the set, skip it.
                currentNode->next = currentNode->next->next;
            } else {
                // Otherwise, move to the next node.
                currentNode = currentNode->next;
            }
        }
        
        return result->next; // Return the new head of the modified list.
    }
};

class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        result = ListNode(0, head)
        nums = set(nums)
        currentNode = result

        while(currentNode.next):
            if(currentNode.next.val in nums):
                currentNode.next = currentNode.next.next
            else:
                currentNode = currentNode.next
        return result.next

Time Complexity

• Constructing the Unordered Set:

  Creating the unordered set numSet from the input vector nums takes \( O(n) \) time, where n is the size of the vector nums.

• Traversing the Linked List:

  The traversal of the linked list takes \( O(m) \) time, where m is the number of nodes in the linked list. For each node, we perform a constant-time check to see if the node’s value is in the unordered set.

• Overall Time Complexity:

  The overall time complexity is \( O(n + m) \), where n is the size of the input vector nums and m is the number of nodes in the linked list.

Space Complexity

• Space for the Unordered Set:

  The unordered set numSet is used to store the elements of the input vector nums. This requires \( O(n) \) space, where n is the size of the vector nums.

• Space for the Result List:

  The dummy node result is created to handle edge cases, but it does not increase the space complexity significantly. The rest of the nodes in the linked list are reused, so no additional space is required for them.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the storage required for the unordered set numSet.