Why it works
- fast starts n nodes ahead and both then move one step at a time, so the gap stays n. When fast is on the last node, slow is n + 1 from the end: right before the node to remove.
- To remove a node you relink the node in front of it. The dummy gives even the head a node in front, so n equal to the length needs no special case: slow simply never leaves the dummy.
- For the same reason the answer is dummy.next, not head: when the head is removed, head still points at it.
Complexity
Time O(L), L the length of the list: fast walks it once, and slow walks behind it. Memory O(1): two pointers and one dummy node.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗