Skip to content
16-Week DSA Roadmap
LeetCode #19MediumProblem 7 of 8

Remove Nth Node From End of List

Delete the n-th node counted from the end in one pass, using two pointers n apart and a dummy node in front of the head.

  • Two pointers with a gap
  • Dummy (sentinel) head node

Before this, know: What a linked list is (see the week 4 overview), The dummy node idea (Merge Two Sorted Lists)

The problem in plain English

You get head, the first node of a linked list, and a number n. Remove the n-th node from the end and return the head of the changed list. n = 1 means the last node, n = 2 the one before it, and so on.

12345
head = [1, 2, 3, 4, 5], n = 2: the 2nd node from the end is 4. Node 3 now skips straight to 5, giving 1 → 2 → 3 → 5.

To remove a node from a linked list, we don’t delete it directly. We change the node before it to point past it: before.next = before.next.next. Then nothing points at the removed node, and it’s no longer part of the list.

The rules that matter:

  • n is always valid: 1 ≤ n ≤ length.
  • n can equal the length. Then the node to remove is the head itself, which has no node before it. This is the edge case that breaks most first attempts.
  • Follow-up: can you do it in one pass?

Before you code: think it through

A linked list doesn’t know its length, and we can’t index from the back. But we can make that stick out of two pointers with a fixed gap between them:

  1. Move fast ahead by n nodes.
  2. Then move fast and slow together, one step each, so the gap never changes.
  3. When fast reaches the end, slow is n nodes behind the end.

We want slow to stop on the node before the target (so it can skip over it). That’s why both pointers start on a dummy node placed in front of the head: it shifts slow back by one, and it also gives the head a node before it.

Pause and think

head = [1, 2, 3], n = 3 (remove the head). Without a dummy node, which node should 'the node before the target' be?

Approach 1: Two passes (count, then walk)

Walk the list once to count its length. The target is at index length − n (counting from 0), so walk again to index length − n − 1, the node before it, and skip over the target. Removing the head needs its own special case.

Two passes: count, then walk

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

12345
variables
node
1node
n
2
length
1
  • Counted
  • Pointer is here
  • Node to remove
  • Answer

Pass 1: count node 1. length = 1.

Step 1 / 10

Which line is running?

function removeNthFromEnd(head, n) {  let length = 0;  let node = head;  while (node !== null) { // pass 1: count the nodesRunning now:     length++;    node = node.next;  }  if (n === length) return head.next; // removing the head itself  let before = head; // pass 2: stop just before the target  for (let i = 1; i < length - n; i++) {    before = before.next;  }  before.next = before.next.next; // skip over the target  return head; // the head didn't change}

Two passes

function removeNthFromEnd(head, n) {  let length = 0;  let node = head;  while (node !== null) { // pass 1: count the nodes    length++;    node = node.next;  }  if (n === length) return head.next; // removing the head itself  let before = head; // pass 2: stop just before the target  for (let i = 1; i < length - n; i++) {    before = before.next;  }  before.next = before.next.next; // skip over the target  return head; // the head didn't change}
def remove_nth_from_end(head, n):    length = 0    node = head    while node is not None:  # pass 1: count the nodes        length += 1        node = node.next    if n == length:        return head.next  # removing the head itself    before = head  # pass 2: stop just before the target    for _ in range(length - n - 1):        before = before.next    before.next = before.next.next  # skip over the target    return head  # the head didn't change

Why not stop here?

It’s correct and still O(n): for 5 nodes, about 5 + 3 = 8 steps. But it reads the list twice, and the interviewer’s follow-up asks for one pass. It also needs the n === length special case. The one-pass version fixes both: the dummy node removes the special case, and the gap removes the counting pass.

The pattern: two pointers with a gap

Pattern

Two pointers with a gap

Template

Use it when: you need a position measured from the END of a linked list (or any one-way sequence) in a single pass.

Signal words

  • “n-th from the end”
  • “k-th last”
  • “one pass”
  • “remove from end”
  • “rotate list”

Approach 2: Dummy node + gap of n

  1. Make dummy with dummy.next = head. Put both fast and slow on it.
  2. Move fast forward n times.
  3. While fast.next isn’t null, move both one step.
  4. Now slow.next is the target. Skip it: slow.next = slow.next.next.
  5. Return dummy.next (the head may have been removed).

The red node is the one we’ll remove. Watch the gap stay at n while both pointers slide. Then try n = length: slow never leaves the dummy, and the head is removed with exactly the same line.

Dummy node + two pointers n apart

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

D12345
variables
slow
Dnode
fast
Dnode
n
2
gap (fast − slow)
0
  • Node to remove
  • slow
  • fast
  • Link just rewired
  • Dummy / removed
  • Answer

Goal: remove the 2nd from the end node (n = 2), which is node 4 (red). Put a dummy node "D" in front of head, and start both slow and fast on it. The dummy means even the head has a node before it.

Step 1 / 9

Which line is running?

function removeNthFromEnd(head, n) {Running now:   const dummy = new ListNode(0, head); // sits before head, so even head can be removed  let fast = dummy;  let slow = dummy;  for (let i = 0; i < n; i++) {    fast = fast.next; // give fast a head start of n nodes  }  while (fast.next !== null) { // until fast stands on the last node    fast = fast.next;    slow = slow.next;  }  slow.next = slow.next.next; // slow is just before the target: skip it  return dummy.next;}

The code, line by line

Dummy node + gap of n

function removeNthFromEnd(head, n) {  const dummy = new ListNode(0, head); // sits before head, so even head can be removed  let fast = dummy;  let slow = dummy;  for (let i = 0; i < n; i++) {    fast = fast.next; // give fast a head start of n nodes  }  while (fast.next !== null) { // until fast stands on the last node    fast = fast.next;    slow = slow.next;  }  slow.next = slow.next.next; // slow is just before the target: skip it  return dummy.next;}
def remove_nth_from_end(head, n):    dummy = ListNode(0, head)  # sits before head, so even head can be removed    fast = dummy    slow = dummy    for _ in range(n):        fast = fast.next  # give fast a head start of n nodes    while fast.next is not None:  # until fast stands on the last node        fast = fast.next        slow = slow.next    slow.next = slow.next.next  # slow is just before the target: skip it    return dummy.next

The line numbers match up to line 6; after that JavaScript’s closing braces put it one line ahead. LeetCode provides ListNode(val, next); in Python the method is def removeNthFromEnd(self, head, n) inside class Solution.

  • Line 2: the dummy node, pointing at the real head. Its value (0) never matters.
  • Lines 3–4: both pointers start on the dummy, not the head. Starting one node early is what makes slow stop before the target.
  • Lines 5–6: the head start. After this, fast is exactly n nodes ahead. It never falls off the list, because n ≤ length.
  • Line 8 (JS) / 7 (Py): stop when fast is on the last node (its next is null). Using fast.next here, not fast, is what leaves slow one node before the target.
  • Lines 9–10 (JS) / 8–9 (Py): move both together; the gap stays n.
  • Line 12 (JS) / 10 (Py): unlink the target by pointing past it.
  • Line 13 (JS) / 11 (Py): return dummy.next, not head: if we removed the head, head still points at the removed node.

Dry run

head = [1, 2, 3, 4, 5], n = 2, so the target is node 4. D is the dummy:

phaseslowfastgapnote
startDD0both on the dummy
head start 1D11
head start 2D22gap is now n
together132
together242
together352fast.next is null: stop
remove35—3.next = 5 (skips 4)
head = [1, 2, 3, 4, 5], n = 2

When fast stops on 5 (the last node), slow is on 3: exactly the node before the 2nd-from-last. Result: 1 → 2 → 3 → 5.

Complexity

Two passes

Time

O(n)

One full pass to count, then a partial pass to the node before the target.

Space

O(1)

A counter and one pointer.

Dummy node + gap

Time

O(n)

fast walks the list once; slow follows behind. One pass in total.

Space

O(1)

The dummy node and two pointers.

Both are O(n), but the second reads the list once and has no special case.

Common mistakes and edge cases

What to say out loud:

  1. “The two-pass solution counts the length first; I can do one pass with two pointers n apart.”
  2. “I’ll start both on a dummy node so removing the head isn’t a special case.”
  3. “When fast is on the last node, slow is right before the target, so I skip it.”
  4. “O(n) time, one pass, O(1) space.”

Likely follow-ups:

  • “Return the n-th node from the end instead of removing it.” Same gap, but start both on the head and stop when fast is null; slow is then on that node.
  • “What if n could be larger than the length?” Check that fast isn’t null during the head start, and return the list unchanged if it runs out.

Related problems:

  • Merge Two Sorted Lists: where the dummy node is introduced.
  • Linked List Cycle: two pointers at different speeds rather than a fixed gap.
  • Rotate List (LeetCode 61): find the k-th node from the end with the same gap trick.