Drop the nth node from the end

Remove the nth node counting from the end of the list, and return the head.

Worked example#

For 1 -> 2 -> 3 -> 4 -> 5 with n = 2, the second from the end is 4, so the answer is 1 2 3 5.

Counting from the end without knowing the length#

Start two references at the front and move the first one n steps ahead. Now hold that gap and move both together. When the leading one reaches the end, the trailing one is exactly n from the end.

With n = 2:

The trailing reference is at 3, and 3's next is the node to drop, so point 3 at 5.

To remove a node you need the one before it, which is why the trailing reference is deliberately parked one short.

The case that breaks a first attempt#

What if the node to remove is the head itself, as in 1 -> 2 with n = 2? There is no node before it, so there is nothing to rewire.

A dummy node in front of the head removes the special case entirely: the head now has something before it like every other node, and the answer is dummy.next. Without it you need a separate branch, and forgetting that branch is the usual bug.

The cost#

Time O(n), one pass. Memory O(1).

Constraints#

• 1 <= number of nodes <= 30
• 1 <= n <= number of nodes
• 0 <= value <= 100