Remove Nth Node From End of List

medium linked list two pointers

Problem

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Input1→2→3→4→5, n = 2

Output1→2→3→5

The 2nd-to-last node (4) is unlinked.

list (comma-separated)

n (1-indexed from end)

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

function removeNthFromEnd(head, n) {
  const dummy = { val: 0, next: head };
  let fast = dummy, slow = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next;
  while (fast) { fast = fast.next; slow = slow.next; }
  slow.next = slow.next.next;
  return dummy.next;
}

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 != null) { fast = fast.next; slow = slow.next; }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode *fast = &dummy, *slow = &dummy;
    for (int i = 0; i <= n; ++i) fast = fast->next;
    while (fast) { fast = fast->next; slow = slow->next; }
    slow->next = slow->next->next;
    return dummy.next;
}

Explanation

The clever idea is a two-pointer gap: move one pointer n steps ahead of another, then slide both together. When the front pointer reaches the end, the back pointer is sitting right before the node we want to remove — all in a single pass.

We add a dummy in front so we can delete the real head if needed. We advance fast by n + 1 steps first, which sets the gap so that slow lands on the node just before the target. Then we move fast and slow together until fast falls off the end.

It works because the fixed gap of n + 1 is preserved as both pointers move, so the distance from slow to the end is always exactly n + 1 nodes. That leaves slow perfectly placed to splice with slow.next = slow.next.next.

Example: 1→2→3→4→5, n = 2. After offsetting, slow ends on node 3, so slow.next (the 4, second from the end) is removed, giving 1→2→3→5.

This is a single traversal with constant extra space — no need to first count the length and walk again.

Time: O(L) Space: O(1)