19. Remove Nth Node From End of List

Quick Identifier

Topic: linked-list
Pattern: Fast & Slow Pointers (gap / offset)
Difficulty: Medium
Companies: Amazon, Google, Meta, Apple, Adobe
Frequency: Very High
LeetCode: 19

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Given a singly linked list and nthFromEnd, remove the node that is nthFromEnd steps from the tail and return the head (first node may be removed).

Concept Explanation

Given a singly linked list and nthFromEnd, remove the node that is nthFromEnd steps from the tail and return the head (first node may be removed).

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

“Nth from end” with one pass requirement
Fast pointer leads slow by nthFromEnd gaps
Dummy head simplifies removing the first node

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — two passes: measure length length, remove at index length - nthFromEnd.
Better — one pass with array of pointers — O(n) space.
Optimal — O(n) time / O(1) space — advance fast by nthFromEnd+1 from dummy, then move both until fast hits end; slow.Next is the node to skip.

Optimal Solution

Go

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, nthFromEnd int) *ListNode {
	dummy := &ListNode{Next: head}
	lead := dummy
	for step := 0; step <= nthFromEnd; step++ {
		lead = lead.Next
	}
	trail := dummy
	for lead != nil {
		lead = lead.Next
		trail = trail.Next
	}
	trail.Next = trail.Next.Next
	return dummy.Next
}

JavaScript

class ListNode {
	constructor(val = 0, next = null) {
		this.val = val;
		this.next = next;
	}
}

function removeNthFromEnd(head, nthFromEnd) {
	const dummy = new ListNode(0, head);
	let lead = dummy;
	for (let step = 0; step <= nthFromEnd; step++) {
		lead = lead.next;
	}
	let trail = dummy;
	while (lead !== null) {
		lead = lead.next;
		trail = trail.next;
	}
	trail.next = trail.next.next;
	return dummy.next;
}