Example 1
ready- Input
head = [ 1, 2, 3, 4, 5 ] n = 2- Expected
[ 1, 2, 3, 5 ]- Why
- the second node from the end holds 4
Remove Nth Node From End
35 min · removeNthFromEnd()mediumOpen in LeetCode #19 ↗
The instruction points backward — “remove the third node from the end” — but every link in the list points forward. You need to translate that request into a node you can reach.
A singly linked list is a chain of nodes where each node links only to the next one.
Given a non-empty list and an integer n, remove the node that sits n positions from
the end and return the resulting head. Counting is 1-indexed from the end, so
n = 1 means the tail.
A few ground rules:
nis always valid for the supplied list.- If
nequals the list length, remove the head. - Removing the list's only node returns an empty list.
- Keep every surviving node in its original order.
Constraints
1 <= list length L <= 10_0001 <= n <= L-1_000_000_000 <= Node.val <= 1_000_000_000
Hints
Translate end to front
If the list length is L, the node to remove has zero-based index L - n from the
front. Measuring the length first gives you a clean two-walk solution.
Give the head a predecessor
A dummy node before head means even the real head has a previous node. Then every
removal uses the same link change: previous.next = previous.next.next.
Keep a fixed gap
Start two pointers at the dummy node and move fast forward n times. Move both
until fast reaches the tail; slow will be just before the node to remove.
Follow-up
Can you remove the correct node in one traversal without storing the list's nodes in an array?
Visible cases
Examples
Example 2
ready- Input
head = [ 1 ] n = 1- Expected
[]- Why
- removing the only node leaves an empty list
Example 3
ready- Input
head = [ 1, 2 ] n = 1- Expected
[ 1 ]- Why
- n = 1 removes the tail
Interview signal
Asked at
AmazonMetaGoogle
Length + second walk
First count the nodes. A request for the n-th node from the end becomes zero-based
index length - n from the front. Walk to the node just before that index, then bypass
the target.
A dummy node is a temporary node placed before the real head. It gives the head a
predecessor, so removing index 0 needs no special branch.
def remove_nth_from_end(
head: ListNode | None,
n: int,
) -> ListNode | None:
length = 0
current = head
while current is not None:
length += 1
current = current.next
remove_index = length - n
dummy = ListNode(0, head)
previous = dummy
for _ in range(remove_index):
previous = previous.next
previous.next = previous.next.next
return dummy.nextThe input guarantee 1 <= n <= length ensures both previous and the node after it
exist when that final link changes.
Time O(L) — one full walk to count, then up to one more walk to remove. Space O(1) for a fixed number of references.
Gap pointers
You can make the list measure the distance for you. Place slow and fast at the dummy
node, then move fast ahead by n nodes. That fixed gap means when fast reaches the
tail, slow is exactly one node before the target.
def remove_nth_from_end(
head: ListNode | None,
n: int,
) -> ListNode | None:
dummy = ListNode(0, head)
slow = dummy
fast = dummy
for _ in range(n):
fast = fast.next
while fast.next is not None:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextThe dummy node handles both awkward edges naturally. If n == L, slow never leaves
the dummy and removes the head. If n == 1, slow stops just before the tail.
Time O(L) — fast and slow only move forward, for one traversal overall.
Space O(1) — the gap uses two moving references and one dummy node.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 2, 3, 5 ]
Run: visible + custom · Submit: full suite