Leetcode Daily Question 06/09/2024 - 3217. Delete Nodes From Linked List Present in Array

Problem Description:

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.

class ListNode:
  def __init__(self, val = 0, next = None):
    self.val = val
    self.next = next

from typing import Optional, List
class Solution:
  def modifiedLinkedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
    
    nums_set = set(nums)
    
    dummy = ListNode(-1)
    dummy.next = head
    prev = dummy
    current = head
    
    while current:
      if current.val in nums_set:
        prev.next = current.next 
      else:
        prev = current
      
      current = current.next
      
    return dummy.next

Explanation:

While this is not a hard question. It is difficult to clearly write down the solution. It is best approached by example.

Consider the linked list and nums:

1 -> 2 -> 3 -> 4 -> 5
nums = [1,2,3]

We want to removed node 1, 2, and 3 from the linked list. To do this, we need to keep track of what the next node should be and what the previous node is.

We can do this by introducing a dummy node that points to head. This way we can keep track of where the link list should start incase we need to remove the first node like in this example.

We now introduce a prev node to keep track of what node we should be at currently.

Finally, we introduce a current node to check where our potential next node could be.

prev = dummy -> current = 1 -> 2 -> 3 -> 4 -> 5

# 1 is in nums, so current moves to 2 and prev points to this next node, meaning 1 is skipped.
prev = dummy -> current = 2 -> 3 -> 4 -> 5

# 2 is in nums, so current moves to 3 and prev points to this next node, meaning 2 is skipped.
prev = dummy -> current = 3 -> 4 -> 5

# 3 is in nums, so current moves to 4 and prev points to this next node, meaning 3 is skipped.
prev = dummy -> current = 4 -> 5

# 4 is not in nums, so we move current naturally to the next node and points prev to this.
dummy -> prev = 4 -> current = 5

# Thus, we return dummy.next as our answer.

We can also put nums into a set to make the lookup O(1).

def modifiedLinkedList(nums, head):
  nums_set = set(nums)
  
  dummy = ListNode(-1)
  dummy.next = head
  prev = dummy
  current = head
  
  while current:
    if current.val in nums_set:
      prev.next = current.next
    else:
      prev = current
    current = current.next
  
  return dummy.next

The time complexity is O(n), where n is the number of nodes. This is because we need to traverse the linked list in its entirety exactly once.

The space complexity is O(n), since the worst case if we do not remove any node from our original list.

The full solution can be found near the top of the page.