jeremymanning.md

Problem 3217: Delete Nodes From Linked List Present in Array

Initial thoughts (stream-of-consciousness)

• Let's start by changing nums to a set (instead of a list) so that we can match each value along the linked list to the values in nums in constant time (instead of $O(n)$ time, where $n$ is the length of nums)
• I think there are two cases we need to account for:
  • While the head is in nums, set head = head.next
  • Next, keep looping through the subsequent nodes:
    • If node.val is not in nums, continue to the next node (or return head if node.next is None)
    • If node.valis in nums, we need to snip out the current node by setting prev.next = node.next. So that means we'll also need to keep track of the previous node we've visited

Refining the problem, round 2 thoughts

• Since we're guaranteed that at least one node is not in nums, we don't have to account for the special case where there is no head to return
• The one sort of "tricky" (if it can be called that) piece is how we keep track of the previous node. I think we can start by setting prev = head (once we've skipped ahead to the first node that isn't in nums). Then we can start looping through by setting current = prev.next and then continue until current.next is None.
• Let's try it!

Attempted solution(s)

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution: defmodifiedList(self, nums: List[int], head: Optional[ListNode]) ->Optional[ListNode]: nums=set(nums) whilehead.valinnums: head=head.nextprev=headcurrent=head.nextwhilecurrentisnotNone: ifcurrent.valinnums: prev.next=current.nextcurrent=current.nextelse: prev, current=current, current.nextreturnhead

• Given test cases pass
• Off the top of my head I can't think of any particularly interesting edge cases that I'm not accounting for, so I'll just try submitting 🙂

I'll take it! Solved 🎉!