Remove Nth Node From End of List

Given the head of a linked list and an integer n, remove the nth node from the end of the list and return the head of the modified list.

Examples

• 1 ≤ sz ≤ 30 (number of nodes in the list)
• 0 ≤ Node.val ≤ 100
• 1 ≤ n ≤ sz

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked List Fundamentals — node structure, traversal, and pointer manipulation
• Two Pointers Technique — using multiple pointers to track positions simultaneously
• Dummy Node Pattern — sentinel node to simplify head-deletion edge cases

1. Brute Force (Array)

Intuition

Store all nodes in an array for O(1) random access. The node to remove is at index len - n from the front. Adjusting the previous node's next pointer is then straightforward.

Algorithm

• Traverse and push all nodes into nodes[].
• Compute removeIndex = len(nodes) - n.
• If removeIndex == 0, return head.next (remove head).
• Otherwise: nodes[removeIndex-1].next = nodes[removeIndex].next.
• Return head.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next

        removeIndex = len(nodes) - n
        if removeIndex == 0:
            return head.next

        nodes[removeIndex - 1].next = nodes[removeIndex].next
        return head

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> nodes = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) { nodes.add(cur); cur = cur.next; }

        int removeIndex = nodes.size() - n;
        if (removeIndex == 0) return head.next;

        nodes.get(removeIndex - 1).next = nodes.get(removeIndex).next;
        return head;
    }
}

Time Complexity: O(n)
Space Complexity: O(n) — the nodes array.

2. Iteration (Two Pass)

Intuition

First count the total length N. The node to delete is at position N - n from the front (0-indexed). A second traversal reaches the node just before it and skips it. No extra space beyond a single pointer.

Algorithm

• Traverse once to compute total length N.
• Compute removeIndex = N - n. If 0, return head.next.
• Traverse again, stopping when i + 1 == removeIndex.
• Set cur.next = cur.next.next. Return head.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        N = 0
        cur = head
        while cur:
            N += 1
            cur = cur.next

        removeIndex = N - n
        if removeIndex == 0:
            return head.next

        cur = head
        for i in range(N - 1):
            if (i + 1) == removeIndex:
                cur.next = cur.next.next
                break
            cur = cur.next
        return head

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int N = 0;
        ListNode cur = head;
        while (cur != null) { N++; cur = cur.next; }

        int removeIndex = N - n;
        if (removeIndex == 0) return head.next;

        cur = head;
        for (int i = 0; i < N - 1; i++) {
            if (i + 1 == removeIndex) {
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
        }
        return head;
    }
}

Time Complexity: O(n) — two passes.
Space Complexity: O(1).

3. Recursion

Intuition

Recurse to the end of the list. As the call stack unwinds, decrement a counter n at each node. When n reaches 0, we are at the target node — return head.next to skip it. Otherwise return head to rebuild the list.

Using a mutable container [n] (Python list) or an instance variable (Java) lets the counter be shared across recursive frames.

Algorithm

• Base case: if head is None, return None.
• Recurse: head.next = rec(head.next, n).
• Decrement n[0] -= 1.
• If n[0] == 0, return head.next (skip this node).
• Otherwise return head.

class Solution:
    def rec(self, head, n):
        if not head:
            return None
        head.next = self.rec(head.next, n)
        n[0] -= 1
        if n[0] == 0:
            return head.next
        return head

    def removeNthFromEnd(self, head, n):
        return self.rec(head, [n])

class Solution {
    int n;

    public ListNode removeNthFromEnd(ListNode head, int n) {
        this.n = n;
        return rec(head);
    }

    private ListNode rec(ListNode head) {
        if (head == null) return null;
        head.next = rec(head.next);
        n--;
        if (n == 0) return head.next;
        return head;
    }
}

Time Complexity: O(n)
Space Complexity: O(n) — recursion call stack.

4. Two Pointers (One Pass)

Intuition

Maintain a gap of exactly n nodes between left and right. Start left at a dummy node before the head and right at the head. Advance right by n steps to create the gap. Then advance both pointers together until right hits null. At that moment, left.next is exactly the node to remove.

The dummy node makes it seamless to delete the head — left can sit at the dummy with left.next = head, so removing the first real node is identical to removing any other.

Common Pitfalls

Forgetting to Handle Head Removal

When n equals the length of the list, the head itself must be removed. Without a dummy node, this requires a special case. With a dummy node at position -1, the logic works uniformly — left sits at the dummy and left.next = head is skipped exactly like any other node.

# Without dummy — special case needed:
if removeIndex == 0:
    return head.next

# With dummy — no special case:
dummy = ListNode(0, head)
left = dummy  # left can sit at dummy safely
...
return dummy.next

Off-by-One in Pointer Positioning

right must be advanced exactly n steps (not n-1). After this, left is at the dummy and right is at node n. When both pointers then advance together until right is null, left lands precisely at the node before the target. Advancing right by n-1 causes left to stop one node too late, removing the wrong node.

Not Returning the Updated Head

When using a dummy node, always return dummy.next — not head. If the head was removed, head still points to the old (deleted) first node while dummy.next correctly points to the new head.