Remove Linked List Elements

Create a dummy node whose next points to head, then keep a pointer prev to the last node that will remain in the list. Inspect prev.next rather than inspecting the current node after advancing. If prev.next.val == target, remove it by assigning prev.next = prev.next.next; do not move prev, because the replacement next node may also match. Otherwise advance prev = prev.next. Return dummy.next.

The dummy node removes the special case where the original head, or several initial nodes, must disappear. The invariant is that every node before prev has been examined and retained, while prev.next is the first unprocessed node. Test an empty list, one matching node, no matches, all matches, and runs such as 6 -> 6 -> 1 -> 6. Each node is inspected once, so time is O(n) and auxiliary space is O(1). Do not allocate a replacement list unless immutability is explicitly required.