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.

Why this is worth learning

A fixed pointer gap turns an end-relative rank into a predecessor location. The dummy head makes removing the actual head an ordinary link update.

Before coding: one-minute experiment

For a three-node list, which node is removed when n=3, and why is a dummy useful?

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)

A two-pass baseline measures length L and removes position L−n+1. In one pass, the same arithmetic can be represented by distance between two pointers. Start both at a dummy and advance fast n edges. Moving them together preserves that lead. Stop when fast is the final real node: slow is then the predecessor of the target, including the dummy when the head is removed. This version pairs an n-edge lead with the condition fast.Next!=nil; changing either the lead or stopping condition requires re-deriving the other.

Invariant: After initialization, fast stays exactly n edges ahead of slow; when fast.Next is nil, slow.Next is the node to remove.

Algorithm (step-by-step)

1. Create dummy -> head; initialize both slow and fast to dummy.
2. Advance fast by exactly n edges.
3. While fast.Next != nil, advance both pointers one edge. Stop with fast at the final real node, not at nil.
4. Bypass slow.Next using slow.Next = slow.Next.Next.
5. Return dummy.Next.

Correctness sketch

Start slow and fast at a dummy node and advance fast n edges. Their separation is now n edges. Move both while fast.Next exists; each simultaneous step preserves the gap. At termination fast is the final real node, so slow is immediately before the node with n nodes from itself through the end. Bypassing slow.Next removes exactly the nth node from the end. If n equals the original length, slow remains the dummy and the same assignment replaces the head. Every other node retains its relative order and identity.

Trace (hand walkthrough)

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

Walk:
- initially slow=dummy, fast=dummy
- advance fast 2 edges: dummy->1->2; slow remains dummy
- move together: (slow,fast) = (1,3), then (2,4), then (3,5)
- fast.Next is nil -> bypass slow.Next (node 4) -> 1->2->3->5

Pitfalls to avoid

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

Debugging lens

Use a singleton, removal of the tail, and removal of the head. The contract guarantees 1<=n<=length; do not hide an off-by-one by adding arbitrary invalid-input behavior.

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.

Reconstruction checkpoint

Use a dummy and an n-edge lead to remove the fourth node from the end of A→B→C→D. Where are fast and slow before the paired loop? Why are there zero paired moves?

Return to Linked List · Module quiz