Remove Nth Node From End of List

MEDIUM✓ CHIP-TIMEDLC #19 — FULL STATEMENT ↗

The drill: Remove the node that sits n positions from the end of a singly linked list — measured from the tail, not the head — and hand back the list with that one node gone.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A singly linked list and a whole number n arrive together, and the job is to remove whichever node sits n positions back from the very end of the list — counting from the tail, not the head.

After that one node is unlinked, the rest of the list keeps its original order and wiring, and the new head is handed back — which might be a different node than before if the removed node was the original head.

n is always small enough to point at a real node somewhere in the list, so there's never a question of the target falling outside the list's bounds.

EX 01

head = [1, 2, 3, 4, 5] · n = 2

→ [1, 2, 3, 5]

REMOVAL FROM THE MIDDLE

EX 02

head = [1] · n = 1

→ []

SINGLE NODE REMOVED, LIST BECOMES EMPTY

EX 03

head = [1, 2] · n = 1

→ [1]

REMOVE THE TAIL

list holds up to a few thousand nodes
n always refers to a real, in-bounds node, counted from the tail
removing the head node is a valid case that changes what's returned
only one node is removed, everything else keeps its order

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Copying every value out, deleting the one at the target offset, and rebuilding the list from what's left is honest and correct — but it never reuses a single original node. Could two pointers moving a fixed distance apart find the target using only the nodes you already have?

HINT 2 THE STRUCTURE

A pointer that starts n steps ahead of a second pointer keeps that exact gap for the rest of the walk. When the lead pointer reaches the last node, where does the trailing pointer have to be sitting?

HINT 3 ONE STEP FROM THE ANSWER

Run a pointer n steps out from a dummy head, then advance it and a second pointer from the dummy together until the leader falls off the end — the trailer is now parked exactly one node before the target, ready to unlink it.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FIXED GAPPATTERN · TWO-POINTER GAPhead = [1, 2, 3, 4, 5] · n = 2

STEP 1

Remove the node 2 from the end of [1, 2, 3, 4, 5] — that's the node holding value 4. A fixed gap between two pointers finds it in one pass.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/remove-nth-node-from-end-of-list.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy

        for _ in range(n):
            fast = fast.next

        while fast.next:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 14 LN

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

        del vals[len(vals) - n]

        dummy = ListNode(0)
        tail = dummy
        for v in vals:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 16 LN

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;

        for (int i = 0; i < n; i++) fast = fast.next;

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 16 LN

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) vals.add(node.val);

        vals.remove(vals.size() - n);

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : vals) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED