Remove Nth Node From End of List

Given the head of a linked list, remove the n-th node from the end of the list and return the head.

Function signature

func RemoveNthFromEnd(head *ListNode, n int) *ListNode

Inputs / outputs

• head: head of the list.
• n: 1-based index from the end.
• Return: new head after removal.

Example

head = 1->2->3->4->5, n=2
Output: 1->2->3->5

Constraints

• 1 <= n <= length of list

Core idea (near-solution)

Use two pointers with a gap of n nodes. When the fast pointer reaches the end, the slow pointer is just before the node to remove.

Invariant: the distance between fast and slow is always n.

Algorithm (step-by-step)

1. Create a dummy node before head.
2. Advance fast by n steps.
3. Move fast and slow together until fast reaches the end.
4. Remove slow.Next.
5. Return dummy.Next.

Correctness sketch

• Invariant: the distance between fast and slow is always n.
• Pointer rewiring preserves all nodes and changes only their order or links.
• Each step maintains list connectivity and the intended invariant.
• When the traversal ends, the list structure matches the required transformation.

Trace (hand walkthrough)

Example input:
head = 1->2->3->4->5, n=2
Output: 1->2->3->5

Walk:
- advance fast 2 steps to node 3
- move slow/fast: slow=2 fast=4; slow=3 fast=5
- fast hits end -> remove slow.next (4) -> 1->2->3->5

Pitfalls to avoid

• Removing the head without a dummy node.
• Off-by-one when advancing fast.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Use a dummy head so removing the original head is uniform.
• Advance fast by n steps, then move slow and fast together.