Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is a singly linked list and a positive integer n.

The task is to delete the node that is n positions from the end and return the new head.

For example, if the list is 1 -> 2 -> 3 -> 4 -> 5 and n = 2, the node to remove is 4, so the result is 1 -> 2 -> 3 -> 5.

The two parts that make people hesitate are:

  • the position is given from the end, not the front
  • removing the head is possible when n equals the full list length

So the real problem is:

find the node just before the target, reconnect its next pointer, and handle the head-removal case cleanly.

The most direct idea

The simplest correct solution is a two-pass approach:

  1. Walk the list once to compute its length.
  2. Convert “the nth node from the end” into “the (length - n)th node from the front.”
  3. Walk again to the node right before that position and unlink the target.

This already gives:

  • Time: O(L)
  • Extra space: O(1)

That is a perfectly acceptable solution in many real codebases because it is easy to reason about and easy to test.

How to derive the one-pass solution

The interview-favorite improvement is to avoid the initial length pass.

The key trick is to keep two pointers separated by exactly n + 1 nodes, using a dummy node placed before the real head.

Why n + 1 instead of n?

Because the algorithm does not just want the target node. It wants the node before the target so it can relink next in one step.

The process is:

  1. Create a dummy node whose next points at head.
  2. Move a leader pointer n + 1 steps ahead from the dummy.
  3. Start a follower pointer at the dummy.
  4. Move both pointers forward together until leader reaches the end.
  5. At that moment, follower.next is exactly the node that should be removed.

This works because the gap between the two pointers never changes. So when the front pointer falls off the list, the back pointer is still exactly one node before the target.

The dummy node is what makes the head-removal case disappear as a special case. If the first real node must be removed, the dummy simply becomes its predecessor.

Why this is the best general answer

The one-pass two-pointer solution is usually the best answer to present first in an interview:

  • Time: O(L)
  • Extra space: O(1)
  • It handles removing the head without branching into awkward special logic
  • It keeps the code short while still being easy to justify

The two-pass solution has the same asymptotic complexity and is also good to mention. But when an interviewer asks for the optimal approach, they usually want the one-pass pointer-gap idea.

Why the one-pass solution is correct

The core invariant is:

the leader pointer always stays exactly n + 1 nodes ahead of the follower pointer.

After the initial advance, both pointers move one step at a time, so that distance stays fixed.

When leader becomes None, it has already moved past the last node. Because the gap is still n + 1, the follower pointer must be sitting immediately before the node that is n positions from the end.

That is exactly the position the algorithm needs, because deleting a node in a singly linked list is really a matter of changing the predecessor’s next pointer.

Python solution

The implementation below uses a sentinel node and a small helper to keep the pointer-gap logic explicit. It also includes defensive validation, even though LeetCode guarantees that n is valid.

from typing import Optional


# LeetCode provides the ListNode class.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def removeNthFromEnd(
        self,
        head: Optional["ListNode"],
        n: int,
    ) -> Optional["ListNode"]:
        if n <= 0:
            raise ValueError("n must be a positive integer")

        sentinel = ListNode(0, head)
        predecessor = self._find_predecessor_of_nth_from_end(sentinel, n)

        target_node = predecessor.next
        if target_node is None:
            raise ValueError("n must refer to an existing node")

        predecessor.next = target_node.next
        return sentinel.next

    def _find_predecessor_of_nth_from_end(
        self,
        sentinel: "ListNode",
        n: int,
    ) -> "ListNode":
        leader = self._advance(sentinel, n + 1)
        follower = sentinel

        # Keep the pointer gap fixed until the leader falls off the list.
        while leader is not None:
            leader = leader.next
            follower = follower.next

        return follower

    @staticmethod
    def _advance(
        node: Optional["ListNode"],
        steps: int,
    ) -> Optional["ListNode"]:
        current = node

        for _ in range(steps):
            if current is None:
                raise ValueError("n is larger than the linked list length")
            current = current.next

        return current

Interview follow-ups

Could you solve it in two passes instead of one?

Yes. First compute the full list length, then convert “remove the nth node from the end” into “remove the (length - n)th node from the front.” After that, walk to the predecessor and unlink the target. This works because once the length is known, the target position is completely determined. The complexity is still O(L) time and O(1) extra space, so it is not asymptotically worse. The tradeoff is practical rather than theoretical: it uses two traversals instead of one, but many people find it easier to derive and less error-prone on a whiteboard.

Why is the dummy node so useful here?

Without a dummy node, removing the head becomes a special case because the head has no predecessor. The sentinel fixes that by pretending there is always one extra node before the real list. Then every deletion looks the same: find the predecessor, skip the target, and return sentinel.next. This does not change the complexity at all, but it makes the implementation much cleaner and avoids branching logic like “if the node to delete is the head, do something different.” In linked-list interviews, a dummy node is often the difference between a brittle solution and a robust one.

What if n might be invalid in production code?

LeetCode guarantees valid input, but production code usually should not assume that. One option is what the solution above does: validate while advancing the lead pointer and fail fast if the list is too short or if n <= 0. Another option is to use the two-pass length-based approach, because after the first pass it is trivial to verify whether 1 <= n <= length. The one-pass version keeps the same O(L) time and O(1) space even with validation, but the two-pass version can be a little easier to reason about if input contracts are loose.

Could this be done recursively?

Yes. A recursive solution can walk to the end first, then count backward during stack unwinding until it reaches the nth node from the end. That works because the recursion stack naturally reverses the traversal order. The downside is that it uses O(L) extra stack space, while the iterative two-pointer solution uses O(1) extra space. In Python especially, recursion is usually the weaker answer because it adds stack overhead and can hit recursion-depth limits on longer lists.