Remove Nth Node From End of List

LINKED LIST · MEDIUM

Builds on Day 15: Linked Lists

Both solutions below assume you’re comfortable walking a singly-linked list node by node and splicing a node out by reassigning a .next pointer; read that lesson first if linked-list traversal is still a new idea.

The problem

You’re given the head of a singly-linked list and an integer n. Remove the nth node counting from the end of the list, and return the (possibly new) head. The tricky part is “from the end” — a singly-linked list only lets you walk forward, so you can’t just look backward n steps from the tail the way you could with an array index.

For example, list = [1,2,3,4,5], n = 2 removes the 2nd-from-end node — that’s the node with value 4 — leaving [1,2,3,5]. list = [1], n = 1 removes the only node, leaving [] (an empty list — the function must return a new head, since the original head no longer exists). list = [1,2], n = 2 removes the 2nd-from-end node, which is the head itself — leaving [2], and this is exactly the edge case that trips up naive implementations that assume the node being removed always has a predecessor.

Solution 1: Two-pass — count the length, then walk to the target

The most direct way to translate “nth from the end” into something a forward-only list can act on: first find out how long the list is. Once you know the total length L, the node to remove is simply at position L - n counting from the head (0-indexed) — an ordinary forward index. A second walk from the head, this time stopping one node early (at position L - n - 1), lands you on the node right before the target, which is exactly what you need to splice it out.

A dummy/sentinel node placed just before the real head sidesteps the “removing the head itself” edge case: instead of writing a special-case check for “is the target the head?”, the walk always starts one step earlier, at the dummy, so the node “right before the target” is reachable through the exact same loop even when the target IS the original head.

This genuinely takes two full passes over the list — the first counts length end-to-end, the second walks up to (but not always all the way to) the end again. Both passes are still O(n) individually, so the whole thing is O(n) time overall; it just does more total work in practice than the one-pass version below.

list = [1, 2, 3, 4, 5], n = 2 — pass 1 counts all 5 nodes, then pass 2 walks 3 hops from the dummy head to land on node 3 (the node right before the target, 4)

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

The code

function removeNthFromEndTwoPass(head, n) {
  const dummy = { val: 0, next: head };

  // Pass 1: walk the whole list once to count its length.
  let length = 0;
  let cur = head;
  while (cur) {
    length++;
    cur = cur.next;
  }

  // Pass 2: walk from the dummy for (length - n) hops. That lands on the
  // node at index (length - n - 1) — the one right BEFORE the target.
  let prev = dummy;
  for (let i = 0; i < length - n; i++) {
    prev = prev.next;
  }

  // Splice the target out.
  prev.next = prev.next.next;
  return dummy.next;
}

Line by line:

• const dummy = { val: 0, next: head }; — a sentinel node placed before the real head. Every walk in this function starts from dummy, never from head directly, so “the node before the target” is always reachable through the exact same code path even when the target is the original head.
• Pass 1’s while loop is a plain full traversal — nothing is removed yet, it only counts. After the loop, length holds the total node count.
• for (let i = 0; i < length - n; i++) — dummy sits one position “before” the head (call that index -1), so reaching index length - n - 1 (the node before the target) takes exactly length - n hops from the dummy. Off-by-one here is the classic bug in this solution — it’s easy to write length - n - 1 hops by mistake and land one node too early.
• prev.next = prev.next.next; — the actual removal. prev.next is the target node; reassigning it to prev.next.next skips over the target entirely, and nothing still points to it.
• return dummy.next; — not head. If the target was the original head, head itself is now a dangling, removed node; dummy.next is always the correct current head, whether or not the head changed.

Complexity

Time	Space	Approach
O(n)	O(1)	Two passes: count the length, then walk to the node before the target

Solution 2: Optimal — one-pass fast/slow pointers

The two-pass version’s real inefficiency is that it doesn’t know where the target is until it’s already walked the whole list once. The fix: keep two pointers, slow and fast, both starting at a dummy head, but give fast a head start of n + 1 steps before slow moves at all. From then on, advance both one step at a time until fast falls off the end of the list (null). The fixed gap between them means that the instant fast runs out of list, slow is sitting exactly one node before the target — no separate counting pass required.

The gap size is the one genuinely non-obvious detail: it has to be n + 1, not n. A gap of n would land slow directly on the target when fast exhausts the list — one node too late to do a clean slow.next = slow.next.next splice, since by then slow would need to reach ahead of itself. The extra +1 is exactly what buys the “one node before” position. The same dummy-head trick from solution 1 still handles removing the actual head node without a special case.

list = [1, 2, 3, 4, 5], n = 5 — fast gets a head start of 6 (5 + 1) steps, then both pointers advance together until fast hits null — slow ends up exactly one node before the target

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

The code

function removeNthFromEndOnePass(head, n) {
  const dummy = { val: 0, next: head };
  let slow = dummy;
  let fast = dummy;

  // Give fast a head start of n + 1 steps — not n. That extra step is what
  // leaves slow exactly one node before the target once fast falls off.
  for (let i = 0; i < n + 1; i++) {
    fast = fast.next;
  }

  // Advance both one step at a time until fast runs out of list.
  while (fast !== null) {
    slow = slow.next;
    fast = fast.next;
  }

  // slow is now the node right before the target — splice it out.
  slow.next = slow.next.next;
  return dummy.next;
}

Line by line:

• let slow = dummy; let fast = dummy; — both pointers start at the sentinel, not the real head, for the same reason as solution 1: it makes “the node before the target” reachable uniformly, even when the target is the original head.
• for (let i = 0; i < n + 1; i++) fast = fast.next; — the head start. Gapping by n + 1 instead of n is the detail that makes the rest of the algorithm work; get this wrong and slow ends up on the target itself instead of one node before it.
• while (fast !== null) { slow = slow.next; fast = fast.next; } — the one and only pass. Both pointers move together, one step each, preserving the fixed gap set up above, until fast walks off the end of the list.
• slow.next = slow.next.next; — identical splice logic to solution 1, just reached without a separate counting pass.
• return dummy.next; — same reasoning as solution 1: correct whether or not the original head was the node removed.

Complexity

Time	Space	Approach
O(n)	O(1)	One pass: n+1-step gap, then advance both pointers together

Complexity comparison

Solution	Time	Space
Two-pass (count, then walk)	O(n)	O(1)
One-pass (fast/slow gap)	O(n)	O(1)

Both solutions are O(n) time and O(1) space — this is not a case of a dramatic asymptotic improvement, and it would be dishonest to claim one. The two-pass version does up to 2n total node visits (a full pass to count, then up to another full pass to walk to the target); the one-pass version does roughly n total node visits (plus the initial n+1-step head start, still O(n) overall). The real, honest win is halving the total traversal work in practice — a genuine but modest improvement, still squarely the same complexity class.

Interview corner

Q: Why does using a dummy/sentinel head node simplify removing the actual head of the list, compared to not using one?

• Without a dummy, removing any interior node is a uniform “reassign the previous node’s .next” operation — but removing the head has no previous node to reassign, so it needs its own special-case branch (typically if (targetIsHead) return head.next;).
• With a dummy placed one position before the real head, dummy.next is the head. That means “the node before the target” is always a real, reachable node — even when the target is the original head — so the exact same splice logic (prev.next = prev.next.next) handles every case, head included, with zero branching.
• The function then returns dummy.next instead of the original head variable — which matters precisely because head may no longer be part of the list by the time the function returns.

Q: In the one-pass solution, why must fast get a head start of exactly n + 1 steps, not n?

• The goal is for slow to land on the node right before the target — not on the target itself — at the moment fast runs out of list, because a clean splice needs the predecessor, not the target.
• A gap of exactly n would leave slow sitting directly on the target when fast becomes null — one node too far, with no way to reach back to the predecessor without an extra pointer.
• The extra +1 is what shifts slow’s eventual resting spot back by exactly one node, landing it on the predecessor instead — which is exactly what slow.next = slow.next.next needs to work correctly.

↳ Common follow-up: “What if you moved fast n steps instead and just tracked one extra ‘previous of slow’ pointer?” That works too — it’s a legitimate variant — but it adds a second tracking variable to do the same job the +1 gap already does for free.

Q: Is the one-pass solution actually asymptotically faster than the two-pass one? What’s the honest way to describe the difference?

• No — both are O(n) time and O(1) space. Calling one-pass “optimal” here refers to doing less total work, not a different Big-O class; it would be inaccurate to claim the one-pass version is asymptotically faster.
• The concrete difference: two-pass does up to 2n total node visits (one full pass to count, then up to another full pass to reach the target); one-pass does about n total node visits.
• That’s a real, practical win — roughly half the traversal work — just not a change in complexity class. Some problems genuinely have a brute-force-vs-optimal story with a true asymptotic gap; this one doesn’t, and it’s worth being able to say so precisely in an interview rather than reflexively claiming a bigger win than what’s actually there.

Q: Trick question — both solutions above check fast !== null (or walk until a .next read returns null) to know when they’ve run off the end of the list. What actually happens if the tail node’s next field is left as undefined instead of explicitly set to null — say, built with { val: 5 } instead of { val: 5, next: null }?

console.log(undefined === null); // ?
console.log(undefined == null);  // ?
// tail.next left undefined, loop checks `cur !== null`:
// while (cur !== null) { cur = cur.next; }

• Answer: undefined === null is false, and undefined == null is true — strict and loose equality disagree here, and this code uses strict (!==).
• Because the loop’s exit condition is cur !== null, an undefined tail .next does NOT satisfy it — the loop treats “haven’t hit null yet” as still true and executes one more iteration.
• That next iteration then tries to read .next off an undefined value and throws TypeError: Cannot read properties of undefined (reading 'next') — a hard crash, not a silent infinite loop and not a quiet miss. Verified directly: a list built with an explicit next: null tail walks cleanly to the end, while the same list with the tail’s next field simply omitted throws exactly that error the moment traversal tries to step past it.

⚠ Trap: this is exactly why both solutions’ list-building helper always writes { val: v, next: null } explicitly, never just { val: v } — an omitted field is undefined, not null, and this code’s strict !== null-checks don’t treat the two as interchangeable the way loose == would.

Quiz

Quiz: 1. What is the honest complexity relationship between the two-pass and one-pass solutions?

Both are O(n) time and O(1) space — one-pass just does roughly half the total traversal work

Both solutions are O(n) time and O(1) space — one-pass just does about half the total node visits (n vs up to 2n). That’s a real practical win, but not a different complexity class.

Quiz: 2. Why do both solutions use a dummy/sentinel head node?

So removing the actual head node uses the same splice logic as any other node, with no special case

Without a dummy, removing the head needs its own special-case branch, since there’s no previous node to reassign. With a dummy placed before the real head, the node before the target is always reachable through the same splice logic, head included.

Quiz: 3. In the one-pass solution, why must fast get a head start of n + 1 steps rather than n?

A gap of n would land slow directly on the target instead of the node before it, when fast hits null

A gap of n would land slow directly on the target instead of the node before it when fast hits null — one node too late for a clean splice.

Quiz: 4. In the two-pass solution, what is the purpose of pass 1?

To count the total length of the list, so pass 2 knows how many hops to make

Pass 1 is a plain full traversal that counts the total number of nodes. Pass 2 then uses that length to compute exactly how many hops from the dummy reach the node right before the target.

Quiz: 5. If a linked list’s tail node has its next field left as undefined (never explicitly set to null), and the traversal loop checks cur !== null, what actually happens?

The loop doesn’t stop at the tail — the next iteration throws a TypeError reading .next off undefined

Array/loop code here checks cur !== null (strict). undefined !== null is true, so a tail with next left undefined does not stop the loop — the next iteration reads .next off undefined and throws a TypeError, rather than looping forever or silently misbehaving.