#29

Remove Nth Node From End of List

medium

linked-listtwo-pointers

Given the head of a singly linked list and an integer n, remove the n-th node counting from the end of the list and return the head of the resulting list.

n is 1-indexed from the end: n = 1 removes the last node, n = 2 removes the second-to-last, and so on. n is always a valid position, so 1 <= n <= length. If the list had a single node, removing it leaves the empty list.

Lists are shown in array notation for readability — [1, 2, 3, 4, 5] is the chain 1 -> 2 -> 3 -> 4 -> 5, and the empty list is [].

Example

Input: head = [1,2,3,4,5]12345nulln = 2

Output: [1,2,3,5]1235null

Counting from the end, the 2nd node is 4; removing it leaves 1 -> 2 -> 3 -> 5.

Constraints

The number of nodes in the list is in the range [1, 30].
0 <= Node.val <= 100
1 <= n <= the number of nodes in the list.

Intuition

Counting from the end is awkward in a singly linked list — you can only walk forward. The obvious fix is two passes: walk once to measure the length L, then walk again to the (L - n)-th node (the one just before the target) and splice the target out.

function removeNthFromEnd(head, n) {
  // First pass: count the nodes.
  let length = 0;
  for (let node = head; node; node = node.next) length++;
  // A dummy before the head lets us delete the head uniformly.
  const dummy = new ListNode(0, head);
  // Second pass: stop on the node just before the target.
  let prev = dummy;
  for (let i = 0; i < length - n; i++) prev = prev.next;
  prev.next = prev.next.next; // skip the target
  return dummy.next;
}

Brute force — measure length, then walk to the predecessor: two passes, O(L).

Two passes is fine — O(L) — but interviewers usually want the one-pass version, which also reveals a reusable trick. Can we find the predecessor without first knowing L?

The key observation: fix a gap between two pointers. If fast is exactly n + 1 nodes ahead of slow, then when fast walks off the end, slow is sitting n + 1 from the end — i.e. on the node just before the one to remove. This is the Two pointers gap technique applied to nodes.

Start both at a dummy before the head, advance fast by n + 1, then move both together until fast is null. One splice and we're done.

Note on the model: the stored solution opens the gap with the loop for (i = 0; i <= n; i++) fast = fast.next — that's n + 1 iterations, the same n + 1 gap described here. Walking it through on 1 -> 2 -> 3 -> 4 -> 5 with n = 2 (remove the 4):

remove 2nd-from-end of 1 -> 2 -> 3 -> 4 -> 5

slow↓fast↓

null

Both start on the dummy `d` (index 0). We'll open a gap of n + 1 = 3 between them.

slow↓

fast↓

null

advance fast n + 1 = 3 steps

fast jumps to node 3 (value 3). The gap from slow to fast is now 3 nodes.

slow↓

fast↓

null

move both together

Lockstep step 1: slow → value 1, fast → value 4. The gap is preserved.

slow↓

fast↓

null

move both together

Lockstep step 2: slow → value 2, fast → value 5 (the last node).

slow↓

fast↓

null

fast = null → splice

fast fell off the end. slow sits on value 3 — exactly the node before the target.

slow↓

null

slow.next = slow.next.next

Skip node 4 by relinking value 3 straight to value 5. Result: 1 -> 2 -> 3 -> 5.

Optimization

Two pointers, one pass

Use a dummy node before the head so removing the real head needs no special case. Advance a fast pointer n + 1 steps from the dummy, then move fast and slow together until fast falls off the end. At that point slow sits on the node just before the one to remove, so slow.next = slow.next.next splices it out.

The gap of n + 1 between the pointers guarantees slow stops one short of the target. Single traversal, no length pre-count.

O(L) time where L is the list length, O(1) space.

function removeNthFromEnd(head, n) {
  // Dummy before the head so removing the real head needs no special case.
  const dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;
  // Send fast n + 1 nodes ahead, opening a fixed gap of n + 1 between the pointers.
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }
  // Move both in lockstep; when fast runs off the end, slow sits just before the target.
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }
  // Splice the n-th-from-end node out by skipping over it.
  slow.next = slow.next.next;
  return dummy.next; // skip the dummy; this is the (possibly new) head
}

Complexity analysis

Time complexity: O(L). Here's why:

Advancing fast by n + 1 is at most L steps.
The lockstep walk then covers the remaining nodes — at most L more.

Both phases are linear and there's no nested loop, so the single pass is O(L), where L is the list length. (The two-pass brute force is also O(L), just with two traversals.)

Space complexity: O(1). Here's why:

Only the dummy node and the fast/slow pointers are allocated, independent of L.
The list is edited in place by one pointer reassignment.

No array or copy of the list is made — O(1) auxiliary space.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
head = [1]1nulln = 1	[]null	Single node, n = 1 — removing it leaves the empty list (the dummy makes this uniform).
head = [1,2]12nulln = 2	[2]2null	n = length removes the head; returning `dummy.next` handles it.
head = [1,2]12nulln = 1	[1]1null	Remove the last node of a two-node list.
head = [1,2,3,4,5]12345nulln = 2	[1,2,3,5]1235null	The worked example — remove the 2nd-from-end (4).
head = [2,2,2,2]2222nulln = 2	[2,2,2]222null	Duplicate values — removal is by position, not value.
head = [1,2,3]123nulln = 3	[2,3]23null	n = length again on an odd list — removes the head.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor