#21 · Linked List

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 its head.

MediumLeetCode

Current node
Link just rewired
Done / in result
Marked
Rejected
Dummy head

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Two pointers with a fixed gap

Move a lead pointer n nodes ahead, then advance both pointers together. When lead reaches the end, trail is exactly n nodes behind it, so it sits at a position defined from the END of the list without ever computing the length.

Memory layout

Two node references. The gap is an invariant, not stored data.

Operation	Cost
find node n from end	O(L) time, one pass
extra space	O(1)

Dummy (sentinel) head

Deleting a node means rewiring the PREVIOUS node's next. The head has no previous node, so it needs its own special case. A dummy node in front gives every real node a predecessor.

Memory layout

One extra node (usually stack allocated); the result is dummy.next.

Operation	Cost
delete after a known node	O(1)

Why it fits

A singly linked list can only go forward, but "n-th from the end" is a position relative to the tail; a gap of n between two pointers converts that into "when the front reaches the end".
Stopping trail on the node BEFORE the victim is what lets us delete in O(1): a singly linked list cannot delete a node given only a pointer to that node.
The dummy head turns "remove the head" into the same operation as removing any other node.

Why alternatives degrade

Count the length, then walk:: Correct and O(L), but walks the list twice; the gap technique does one pass (which matters for streams and slow memory).
Array of nodes:: One pass, but O(L) extra memory.
Recursion that counts on the way back:: Elegant, but O(L) call stack, and the head removal still needs a special case.

Four approaches, from naive to production

1 · beginner

Two passes: count, then walk

time O(L)space O(1)

Count the nodes to learn the length L, then walk L − n − 1 steps from the head to the node before the victim and bypass the victim.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    int length = 0;
    for (ListNode* node = head; node; node = node->next) length++;
    if (n == length) return head->next;
    ListNode* node = head;
    for (int i = 0; i < length - n - 1; i++) node = node->next;
    node->next = node->next->next;
    return head;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    int length = 0;
    for (ListNode node = head; node != null; node = node.next) length++;
    if (n == length) return head.next;
    ListNode node = head;
    for (int i = 0; i < length - n - 1; i++) node = node.next;
    node.next = node.next.next;
    return head;
}

def remove_nth_from_end(head, n):
    length = 0
    node = head
    while node:
        length += 1
        node = node.next
    if n == length:
        return head.next
    node = head
    for _ in range(length - n - 1):
        node = node.next
    node.next = node.next.next
    return head

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let length = 0;
  for (let node = head; node; node = node.next) length++;
  if (n === length) return head!.next;
  let node = head!;
  for (let i = 0; i < length - n - 1; i++) node = node.next!;
  node.next = node.next!.next;
  return head;
}

Flaws & bottlenecks

Traverses the list twice, which hurts when nodes are far apart in memory or the list is a stream.
Removing the head is a separate special case (n === length).
Uses non-null assertions that hide crashes when n is out of range.

Interviewer cross-questions

Can you do it in one pass?

Say: Yes: advance a lead pointer n nodes, then move a second pointer alongside it. When lead hits the end, the second pointer is n behind it.

Why walk L − n − 1 steps and not L − n?

Say: To delete a node in a singly linked list you must stop on the node BEFORE it (to rewire its next). That node is at index L − n − 1 (zero-based).

What if n is larger than the list?

Say: The code would crash (length − n − 1 is negative and head.next may be none). Production code validates 1 ≤ n ≤ L first.

2 · intermediate

Array of nodes

time O(L)space O(L)

Push every node into an array. The victim is nodes[length − n]; relink nodes[idx − 1] to nodes[idx].next.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    vector<ListNode*> nodes;
    for (ListNode* node = head; node; node = node->next) nodes.push_back(node);
    int idx = (int)nodes.size() - n;
    if (idx == 0) return head->next;
    nodes[idx - 1]->next = nodes[idx]->next;
    return head;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode node = head; node != null; node = node.next) nodes.add(node);
    int idx = nodes.size() - n;
    if (idx == 0) return head.next;
    nodes.get(idx - 1).next = nodes.get(idx).next;
    return head;
}

def remove_nth_from_end(head, n):
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    idx = len(nodes) - n
    if idx == 0:
        return head.next
    nodes[idx - 1].next = nodes[idx].next
    return head

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const nodes: ListNode[] = [];
  for (let node = head; node; node = node.next) nodes.push(node);
  const idx = nodes.length - n;
  if (idx === 0) return head!.next;
  nodes[idx - 1].next = nodes[idx].next;
  return head;
}

Flaws & bottlenecks

O(L) extra memory for a problem that fits in O(1).
Still needs a special case when the head is the victim (idx === 0).
The array holds every node alive, which matters for very long lists.

Interviewer cross-questions

Why is this still just a two-pass solution?

Say: One pass builds the array, then the index arithmetic is O(1). It is a trade of memory for the second walk.

How do you avoid the idx === 0 special case?

Say: Put a dummy node at the start of the array (or the list). Every real node then has a predecessor.

When would you prefer this?

Say: When you will do several removals or lookups by index afterwards, so paying O(L) memory once buys O(1) access.

3 · advanced

Dummy head + fast/slow gap

time O(L)space O(1)

Start two pointers on a dummy. Move fast n steps ahead, then advance both until fast is on the last node. slow is then right before the victim.

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

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy;
    ListNode 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;
}

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    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

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy;
  let slow: ListNode = dummy;
  for (let i = 0; i < n; i++) fast = fast!.next;
  while (fast!.next) {
    fast = fast!.next;
    slow = slow.next!;
  }
  slow.next = slow.next!.next;
  return dummy.next;
}

Flaws & bottlenecks

Assumes 1 ≤ n ≤ L: for larger n, fast becomes none and the next dereference crashes.
The off-by-one in the loop condition (fast!.next vs fast) decides whether slow lands before or ON the victim.
Does not detach the removed node, so it still references the rest of the list.

Interviewer cross-questions

Why start both pointers on the dummy?

Say: So slow ends on the node BEFORE the victim, even when the victim is the head: then slow is the dummy and dummy.next = head.next removes it.

Why while (fast.next) and not while (fast)?

Say: It stops fast on the last node rather than past it. With a gap of n, slow stops one node earlier than "n-th from the end", exactly the predecessor we need.

Is it really faster than the two-pass solution?

Say: Both are O(L). It makes one traversal rather than 1.5 on average, which matters for cache behavior or when the list is a stream you cannot rewind, but the asymptotics are the same.

4 · expert

Bounds-checked, detached

time O(L)space O(1)

The same single-pass gap technique, hardened: reject n < 1, detect n larger than the list while advancing lead, and clear the removed node's next so it cannot keep the list alive.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (!head || n < 1) return head;
    ListNode dummy(0, head);
    ListNode* lead = &dummy;
    for (int i = 0; i < n; i++) {
        lead = lead->next;
        if (!lead) return head;
    }
    ListNode* trail = &dummy;
    while (lead->next) {
        lead = lead->next;
        trail = trail->next;
    }
    ListNode* removed = trail->next;
    trail->next = removed->next;
    removed->next = nullptr;
    delete removed;
    return dummy.next;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null || n < 1) return head;
    ListNode dummy = new ListNode(0, head);
    ListNode lead = dummy;
    for (int i = 0; i < n; i++) {
        lead = lead.next;
        if (lead == null) return head;
    }
    ListNode trail = dummy;
    while (lead.next != null) {
        lead = lead.next;
        trail = trail.next;
    }
    ListNode removed = trail.next;
    trail.next = removed.next;
    removed.next = null;
    return dummy.next;
}

def remove_nth_from_end(head, n):
    if not head or n < 1:
        return head
    dummy = ListNode(0, head)
    lead = dummy
    for _ in range(n):
        lead = lead.next
        if not lead:
            return head
    trail = dummy
    while lead.next:
        lead = lead.next
        trail = trail.next
    removed = trail.next
    trail.next = removed.next
    removed.next = None
    return dummy.next

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  if (!head || n < 1) return head;
  const dummy = new ListNode(0, head);
  let lead: ListNode | null = dummy;
  for (let i = 0; i < n; i++) {
    lead = lead.next;
    if (!lead) return head;
  }
  let trail = dummy;
  while (lead.next) {
    lead = lead.next;
    trail = trail.next!;
  }
  const removed = trail.next!;
  trail.next = removed.next;
  removed.next = null;
  return dummy.next;
}

Flaws & bottlenecks

Returns the list unchanged for invalid n without telling the caller, which can hide bugs: some APIs prefer to throw.
Mutates the list in place; callers sharing the list see the change.
Clearing removed.next is only meaningful if the node is otherwise kept (e.g. returned or freed manually); in garbage-collected languages it is a minor hygiene step.

Interviewer cross-questions

Why check !lead inside the loop?

Say: If lead falls off the end before n steps, n exceeds the list length. Detecting it there needs no separate length pass and keeps the single-pass guarantee.

Why set removed.next to none?

Say: It breaks the removed node's link into the list. In C or C++ you would free it right after; in managed languages it prevents the node from accidentally retaining the rest of the list.

Should invalid n throw instead?

Say: It depends on the contract. For a public library throw (or return an error), because silently ignoring bad input hides bugs; for LeetCode the constraints guarantee validity.

Synchronized code walkthrough

Showing: Two passes: count, then walk — shares the player above; click any step to jump.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    int length = 0;
    for (ListNode* node = head; node; node = node->next) length++;
    if (n == length) return head->next;
    ListNode* node = head;
    for (int i = 0; i < length - n - 1; i++) node = node->next;
    node->next = node->next->next;
    return head;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    int length = 0;
    for (ListNode node = head; node != null; node = node.next) length++;
    if (n == length) return head.next;
    ListNode node = head;
    for (int i = 0; i < length - n - 1; i++) node = node.next;
    node.next = node.next.next;
    return head;
}

def remove_nth_from_end(head, n):
    length = 0
    node = head
    while node:
        length += 1
        node = node.next
    if n == length:
        return head.next
    node = head
    for _ in range(length - n - 1):
        node = node.next
    node.next = node.next.next
    return head

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let length = 0;
  for (let node = head; node; node = node.next) length++;
  if (n === length) return head!.next;
  let node = head!;
  for (let i = 0; i < length - n - 1; i++) node = node.next!;
  node.next = node.next!.next;
  return head;
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    vector<ListNode*> nodes;
    for (ListNode* node = head; node; node = node->next) nodes.push_back(node);
    int idx = (int)nodes.size() - n;
    if (idx == 0) return head->next;
    nodes[idx - 1]->next = nodes[idx]->next;
    return head;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode node = head; node != null; node = node.next) nodes.add(node);
    int idx = nodes.size() - n;
    if (idx == 0) return head.next;
    nodes.get(idx - 1).next = nodes.get(idx).next;
    return head;
}

def remove_nth_from_end(head, n):
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    idx = len(nodes) - n
    if idx == 0:
        return head.next
    nodes[idx - 1].next = nodes[idx].next
    return head

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const nodes: ListNode[] = [];
  for (let node = head; node; node = node.next) nodes.push(node);
  const idx = nodes.length - n;
  if (idx === 0) return head!.next;
  nodes[idx - 1].next = nodes[idx].next;
  return head;
}

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

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy;
    ListNode 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;
}

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    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

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy;
  let slow: ListNode = dummy;
  for (let i = 0; i < n; i++) fast = fast!.next;
  while (fast!.next) {
    fast = fast!.next;
    slow = slow.next!;
  }
  slow.next = slow.next!.next;
  return dummy.next;
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (!head || n < 1) return head;
    ListNode dummy(0, head);
    ListNode* lead = &dummy;
    for (int i = 0; i < n; i++) {
        lead = lead->next;
        if (!lead) return head;
    }
    ListNode* trail = &dummy;
    while (lead->next) {
        lead = lead->next;
        trail = trail->next;
    }
    ListNode* removed = trail->next;
    trail->next = removed->next;
    removed->next = nullptr;
    delete removed;
    return dummy.next;
}

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null || n < 1) return head;
    ListNode dummy = new ListNode(0, head);
    ListNode lead = dummy;
    for (int i = 0; i < n; i++) {
        lead = lead.next;
        if (lead == null) return head;
    }
    ListNode trail = dummy;
    while (lead.next != null) {
        lead = lead.next;
        trail = trail.next;
    }
    ListNode removed = trail.next;
    trail.next = removed.next;
    removed.next = null;
    return dummy.next;
}

def remove_nth_from_end(head, n):
    if not head or n < 1:
        return head
    dummy = ListNode(0, head)
    lead = dummy
    for _ in range(n):
        lead = lead.next
        if not lead:
            return head
    trail = dummy
    while lead.next:
        lead = lead.next
        trail = trail.next
    removed = trail.next
    trail.next = removed.next
    removed.next = None
    return dummy.next

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  if (!head || n < 1) return head;
  const dummy = new ListNode(0, head);
  let lead: ListNode | null = dummy;
  for (let i = 0; i < n; i++) {
    lead = lead.next;
    if (!lead) return head;
  }
  let trail = dummy;
  while (lead.next) {
    lead = lead.next;
    trail = trail.next!;
  }
  const removed = trail.next!;
  trail.next = removed.next;
  removed.next = null;
  return dummy.next;
}