Cut a value out of the chain
Remove every node holding a given value by making the node before it skip over, with a dummy node at the front so the head is not special. About 14 minutes.
Skip over it
You can't remove a box from a chain by itself. You remove it by making the box before it point past it, to the box after. Then nothing points to the unwanted box any more, and it drops out of the chain.
So stand on the box before the candidate, look at the next box, and if it holds the unwanted value, set your pointer to the next one's next.
dummy = ListNode(0, head)
cur = dummy
while cur.next:
if cur.next.val == target:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next- cur
- 1
Stand on box 1 (the box before the candidate). The next box holds 2, the unwanted value.
The dummy node and the repeated values
The head has no box before it. Put a dummy box in front, pointing at the head, and now every real box has a predecessor. When the loop ends, the answer is whatever the dummy points to, which may be a new head if the old one was deleted.
One more detail: after skipping a box, don't step forward. The next box might hold the value too, as in 3, 3, 3. Only step forward when you did not delete.
A list is 3, 3, 3 and you remove every 3. What does the dummy node end up pointing to?
- ANothing: the result is the empty list
- BThe first 3
- CItself
Show the answer
Nothing: the result is the empty list. Each skip moves the dummy's pointer past a 3, until nothing is left.
Remove a value
Given the head of a singly linked list and a value target, remove every node whose value equals target and return the new head.
head = [1, 2, 2, 3], target = 2 → [1, 3]
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val, target ≤ 1,000,000