# Delete Node from Linked List

The problem may be found on leetcode.

## Analysis

First, if the head has a bad value it must be removed and the head should be updated to the next value. This process should repeat until a head with an acceptable value is found. This head is saved to be returned.

Once an acceptable head is found, unacceptable elements should be removed from the remainder of the array. This involves delinking the inadmissible node from its prior node, and linking the prior node to current nodes next node.

When delinking, the prior node (`lastnode`

) will not be updated on the loop, as the current node (`node`

) just delinked was the prior node. This is best explained visually:

```
Iteration before delinking of 2
--> 1 ----------> 2 -----------> 3 ----------> 4
^lastnode ^node ^node.next
=lastnode.next
Iteration after delinking of 2
--> 1 ----------> 3 -----------> 4
^lastnode ^node ^node.next
Iteration after checking 3
--> 1 ----------> 3 -----------> 4 ^lastnode ^node
```

## Solution

First, it is necessary to implement a linked list. This was done in the prompt, however I decided to add a bit more for my own tests:

```
class ListNode:
int
val: next: Self | None
def __init__(self, val=0, next: Self | None = None):
self.val = val
self.next = next
def __iter__(self):
= self
curr while curr is not None:
yield curr.val
= curr.next
curr
@classmethod
def fromItems(cls, *items: int) -> Self:
if not items:
raise ValueError("At least one item is required.")
= cls(items[0])
head
= head
lastnode for k in range(len(items) - 1):
= items[k + 1]
item = cls(item)
node next = node
lastnode.= node
lastnode
return head
```

Then I implemented a solution roughly as described above.

```
class Solution:
def modifiedList(
self,
list[int],
nums:
head: ListNode,-> Optional[ListNode]:
)
= set(nums)
hashed
# NOTE: Remove any heads that have bad values.
= head
node # already checked
nodelast: ListNode while node is not None:
if node.val not in hashed:
break
= node
nodelast = node.next # type: ignore[assignment]
node
= node
head_final if head_final is None or head_final.next is None:
return head_final
# NOTE: Delink if value is bad. ``nodelast`` should not be incremented
# when a bad value is removed as it is will remain the same.
while node is not None:
if node.val in hashed:
next = node.next
nodelast.= node.next # type: ignore[assignment]
node else:
= node
nodelast = node.next # type: ignore[assignment]
node
return head_final
```

This solution had \(99\%\) quantile runtime and a pathetic \(21\%\) quantile memory usage. This is likely due to using `set`

to make it easier to search for illegal node values - completing the delinks improved the memory performance to the \(44\%\) quantile, a drastic improvement - however it was at the cost of one quantile of runtime. Removing the use of `set`

resulted in the submission exceeding the time limit. The following solution includes delinking and combines both loops into a single while loop:

```
class Solution2:
def modifiedList(
self,
list[int],
nums:
head: ListNode,-> Optional[ListNode]:
)
# NOTE: Remove any heads that have bad values.
= set(nums)
hashed = None
head_final = True
is_head = head
node
nodelast: ListNode
while node is not None:
if is_head:
if node.val not in hashed:
= node
head_final = False
is_head continue
= node
nodelast = node.next # type: ignore[assignment]
node next = None
nodelast.elif node.val in hashed:
next = node.next
nodelast.next = None
node.
= nodelast.next # type: ignore[assignment]
node else:
= node
nodelast = node.next # type: ignore[assignment]
node
return head_final
```

This did drastically improve the memory usage - all the way to the \(71\%\) quantile - however this reduces the runtime quantile to a sad \(27\%\).

## Time Complexity

This solution has linear time complexity, as each node is inspected exactly once.