Fairly simple question to answer. Given a linked list and a value, remove all the nodes that have the given value. Intuition here is to maintain a prev node that will be used to unlink the node with the given value. A gotcha is the fact that the linked list has a head node with the given value.
To remedy this, we use a dummy node that will act as a pseudo-head. The rest of the algorithm requires us to maintain the last time we saw a node that isn’t the given value - this will be prev. curr will be used to evaluate if a node has the given value, and it will be subsequently unlinked.
The solution is as follows:
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = prev = ListNode(-1, head)
curr = head
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return dummy.next_ Time Complexity:
O(n) - We traverse all nodes within the linked list.
_ Space Complexity:
O(1) - We maintain pointers that occupy constant space.