Remove Value Nodes
Problem
Given the head of a singly linked list and a target value, remove every node holding that value and return the head of what remains. Nodes are unlinked rather than copied into a new list, and the surviving nodes keep their original order. The result may be empty.
Examples
Input: head = 1 -> 2 -> 6 -> 3 -> 6, target = 6
Output: 1 -> 2 -> 3Input: head = 7 -> 7 -> 7, target = 7
Output: empty
Why: edge case, every node matches and the list empties outInput: head = empty, target = 1
Output: empty
Why: edge case, there is nothing to removeHints
0 / 3
Removing a node means changing whatever points at it, so the node you are standing on is never the one you can unhook.
Stand on the node before the candidate and inspect its successor. The head has no predecessor, which is the one case that would need its own branch unless you invent one.
Place a throwaway node in front of the head so every real node has a predecessor. Walk with a pointer that inspects the next node: unhook it when it matches and stay put, because the new successor also needs inspecting, and step forward only when it does not match.
Solution
A throwaway node placed before the head gives every real node a predecessor, so deleting the first node uses exactly the same relink as deleting any other. The walker inspects its successor rather than itself, and after an unhook it deliberately stays where it is, because the node that slid into that slot has not been inspected yet. Moving on after an unhook is the classic bug here, since it skips consecutive matches. Time is O(n) and space is O(1).
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def remove_value(head, target):
dummy = Node(0, head) # lets head removal use the same relink
node = dummy
while node.next:
if node.next.val == target:
node.next = node.next.next # unhook, and do not move on
else:
node = node.next
return dummy.next
print(dump(remove_value(build([1, 2, 6, 3, 6]), 6))) # -> [1, 2, 3]
print(dump(remove_value(build([7, 7, 7]), 7))) # -> []
print(dump(remove_value(build([]), 1))) # -> []Stuck on the idea rather than the code? Insert and Delete covers it.