Problem

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.

Examples

Example 1:

 graph LR
     A[1]:::toBeDeleted --> B[2]:::toBeDeleted --> C[3]:::toBeDeleted --> D[4] --> E[5]
 
     classDef toBeDeleted fill:#ffcccc,stroke:#ff0000;
  
1
2
3

Input: nums = [1,2,3], head = [1,2,3,4,5]
Output: [4,5]
Explanation: Remove the nodes with values 1, 2, and 3.

Example 2:

 graph LR
     A[1]:::toBeDeleted --> B[2] --> C[1]:::toBeDeleted --> D[2] --> E[1]:::toBeDeleted --> F[2]
 
     classDef toBeDeleted fill:#ffcccc,stroke:#ff0000;
  
1
2
3

Input: nums = [1], head = [1,2,1,2,1,2]
Output: [2,2,2]
Explanation: Remove the nodes with value 1.

Example 3:

 graph LR
     A[1] --> B[2] --> C[3] --> D[4]
 
     classDef toBeDeleted fill:#ffcccc,stroke:#ff0000;
  
1
2
3

Input: nums = [5], head = [1,2,3,4]
Output: [1,2,3,4]
Explanation: No node has value 5.

Solution

Method 1 - Iteration

Here are the steps:

  1. Convert the nums list to a set: This allows for O(1) average-time complexity checks for whether a value exists in the array.
  2. Traverse the linked list: Iterate through the linked list, removing nodes that contain values present in the set.

Video Explanation

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public ListNode modifiedList(int[] nums, ListNode head) {
        // Convert nums array to a set for O(1) lookup times.
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        // Initialize a dummy node to handle edge cases easily.
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;

        // Traverse the linked list.
        while (curr != null && curr.next != null) {
            if (numSet.contains(curr.next.val)) {
                curr.next = curr.next.next; // Remove the node.
            } else {
                curr = curr.next;
            }
        }

        return dummy.next; // Return the new head.
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def modifiedList(
        self, nums: List[int], head: Optional[ListNode]
    ) -> Optional[ListNode]:
        # Convert nums list to set for O(1) lookup times.
        num_set = set(nums)

        # Initialize a dummy node to handle edge cases easily.
        dummy = ListNode(0)
        dummy.next = head
        current = dummy

        # Traverse the linked list.
        while current and current.next:
            if current.next.val in num_set:
                current.next = current.next.next  # Remove the node.
            else:
                current = current.next

        return dummy.next  # Return the new head.

Complexity

  • ⏰ Time complexity: O(m + n) , where m is the number of elements in nums and n is the number of nodes in the linked list.
  • 🧺 Space complexity: O(m), where m is the number of elements in nums.