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)
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.
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:
nis always valid:1 ≤ n ≤ length.ncan 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?
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:
- Move
fastahead bynnodes. - Then move
fastandslowtogether, one step each, so the gap never changes. - When
fastreaches the end,slowisnnodes 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
There isn’t one: the head is the first node. Code that always does
before.next = before.next.next has nothing to put in before. You’d need a
special case like if (n === length) return head.next.
With a dummy node D → 1 → 2 → 3, the node before the head is D. The same line,
D.next = D.next.next, removes the head, and dummy.next is the new head.
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
- node
- 1node
- n
- 2
- length
- 1
- Counted
- Pointer is here
- Node to remove
- Answer
Pass 1: count node 1. length = 1.
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 changeIt’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.
Pattern
Two pointers with a gap
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”
- Make
dummywithdummy.next = head. Put bothfastandslowon it. - Move
fastforwardntimes. - While
fast.nextisn’t null, move both one step. - Now
slow.nextis the target. Skip it:slow.next = slow.next.next. - 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
- 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.
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;}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.nextThe 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
slowstop before the target. - Lines 5–6: the head start. After this,
fastis exactlynnodes ahead. It never falls off the list, becausen ≤ length. - Line 8 (JS) / 7 (Py): stop when
fastis on the last node (itsnextis null). Usingfast.nexthere, notfast, is what leavesslowone 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, nothead: if we removed the head,headstill points at the removed node.
head = [1, 2, 3, 4, 5], n = 2, so the target is node 4. D is the dummy:
| phase | slow | fast | gap | note |
|---|---|---|---|---|
| start | D | D | 0 | both on the dummy |
| head start 1 | D | 1 | 1 | |
| head start 2 | D | 2 | 2 | gap is now n |
| together | 1 | 3 | 2 | |
| together | 2 | 4 | 2 | |
| together | 3 | 5 | 2 | fast.next is null: stop |
| remove | 3 | 5 | — | 3.next = 5 (skips 4) |
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.
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.
What to say out loud:
- “The two-pass solution counts the length first; I can do one pass with two pointers n apart.”
- “I’ll start both on a dummy node so removing the head isn’t a special case.”
- “When fast is on the last node, slow is right before the target, so I skip it.”
- “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
fastis null;slowis then on that node. - “What if n could be larger than the length?” Check that
fastisn’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.