Remove Nth Node From End of List

The target is named from the end, but a singly linked list only lets you move forward. The key move is to convert that backward-looking position into a fixed pointer gap.

Read the Contract and Find the Real Target

You receive:

• The head of a singly linked list.
• An integer n, where 1 <= n <= length of the list.

Remove the nth node counted from the end and return the resulting head.

Counting starts at the tail:

• n = 1 means remove the last node.
• n = 2 means remove the second-to-last node.
• If n equals the list length, remove the original head.

For example:

1 -> 2 -> 3 -> 4 -> 5
n = 2

The target is node 4, so the result is:

1 -> 2 -> 3 -> 5

The important structural detail is easy to miss: in a singly linked list, removing a node requires access to its predecessor. You cannot move backward from node 4 to node 3. Instead, you need to find node 3 and change its next pointer:

3.next = 5

That is the real target of the search. We are not merely locating the node to delete. We are locating the node immediately before it.

The standard problem asks for the modified head. A one-pass traversal is the follow-up, not the only valid interpretation of the primary contract. I would start with the straightforward two-pass solution, because it gives us a reference model for deriving and debugging the one-pass version.

Build the Two-Pass Baseline

Let L be the list length.

The nth node from the end is at zero-based index:

L - n

For a list of length 5 and n = 2:

5 - 2 = 3

Index 3 contains node 4.

A two-pass solution works like this:

1. Traverse the list and count L.
2. Convert the end-relative position into a forward position.
3. Walk to the predecessor of that position.
4. Bypass the target with one pointer update.

A dummy node makes even the baseline uniform:

dummy -> head -> ...

If the target is the original head, dummy is its predecessor. Otherwise, the predecessor is an ordinary list node.

The mutation is always the same:

predecessor.next = predecessor.next.next

Without a dummy node, removing the original head needs a special branch:

if n == L:
    return head.next

That branch is valid, but it creates a second deletion mechanism. A dummy node removes that split. One predecessor, one rewiring rule, one returned entry point.

The two-pass method still runs in O(L) time and uses O(1) auxiliary space. Its drawback is not asymptotic complexity. It reads the list in two separate traversals. That makes it a useful baseline, but the follow-up asks whether we can preserve the same positioning information while moving forward only once.

Derive the Fixed Gap

The recognition signal is:

• The list is singly linked.
• The target is specified relative to the end.
• You cannot index backward.
• Deletion needs the target's predecessor.
• All pointer movement must be forward.

The missing information is the list length. A lead pointer can carry that information indirectly if it stays a fixed distance ahead of a trailing pointer.

Use a dummy node and place both pointers at it:

dummy -> 1 -> 2 -> 3 -> 4 -> 5
lead
trail

Advance lead by n + 1 links. Then move lead and trail together until lead becomes None.

Why n + 1?

Because trail must stop at the predecessor of the target, not at the target itself. Starting from the dummy adds one extra position to the geometry:

lead is n + 1 links ahead of trail

When lead falls off the list, trail.next is exactly the nth node from the end.

An equivalent convention starts lead at head and advances it by n links. That can also work. The danger is mixing conventions:

• Starting both pointers at dummy requires an n + 1 advance and a lead is None stopping condition.
• Starting lead at head requires an n advance and a different stopping condition.

These are consistent systems. Off-by-one bugs usually come from combining pieces from both.

This is a fixed-gap technique. Both pointers move at the same speed after initialization. It is different from midpoint or cycle-detection techniques where one pointer may move twice as fast as the other. Here, the useful information is distance, not relative speed.

State the Invariant and Prove the Rewire

The core invariant is:

During the paired traversal, lead remains exactly n + 1 links ahead of trail. Therefore, trail.next remains the candidate node to remove.

The initial advancement establishes the gap. Moving both pointers one link per iteration preserves it.

When lead becomes None, it has moved past the final real node. Since trail is n + 1 links behind that off-the-end position, trail is immediately before the nth node from the end.

The deletion is then local:

trail.next = trail.next.next

Suppose the relevant portion is:

trail -> target -> successor

After the assignment:

trail -> successor

Every node before trail remains reachable. Every node after target remains reachable. Only target is removed from the chain.

The dummy node also handles the returned head:

• If the original head stays, dummy.next still points to it.
• If the original head is removed, dummy.next now points to the second node.
• If the list has one node, dummy.next becomes None.

So the correct return value is always:

dummy.next

The values stored in the nodes do not matter. The proof depends on pointer positions, predecessor access, and preservation of the next chain.

Dry-Run the Pointer Positions

Use:

dummy -> 1 -> 2 -> 3 -> 4 -> 5
n = 2

Both pointers start at dummy. Advance lead by n + 1 = 3 links:

trail = dummy
lead  = 3

Now move both together:

Step	trail	lead	Next action
Start after gap	dummy	3	Move both
1	1	4	Move both
2	2	5	Move both
3	3	None	Stop

At the stopping point:

trail      = 3
trail.next = 4

Node 4 is the second node from the end. Bypass it:

3.next = 5

The final list is:

1 -> 2 -> 3 -> 5

Under interview pressure, ask one question before writing the mutation:

Where is the predecessor when the scan stops?

If the answer is not precise, the pointer convention is not finished.

Implement the Python Solution

Assume the usual linked-list node interface:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Here is the one-pass remove nth node Python solution:

from typing import Optional


class Solution:
    def removeNthFromEnd(
        self,
        head: Optional[ListNode],
        n: int
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        trail = dummy
        lead = dummy

        # Create a gap of n + 1 links from trail to lead.
        for _ in range(n + 1):
            lead = lead.next

        # Preserve the gap while scanning toward the end.
        while lead is not None:
            trail = trail.next
            lead = lead.next

        # trail is immediately before the node to remove.
        trail.next = trail.next.next

        return dummy.next

Each part has one obligation:

• dummy gives every removable node a predecessor.
• lead creates the end-relative positioning information.
• trail follows at a fixed distance.
• The loop stops with trail at the target's predecessor.
• The single rewiring removes the target.
• dummy.next returns the correct head.

The initial advancement is safe because the contract guarantees n <= length of the list. Starting at dummy, advancing n + 1 links reaches either a real node or None; it does not need invalid-input handling outside the stated constraints.

Notice that positioning and mutation are separate. First establish the pointer state. Then perform the destructive update. This makes the code easier to inspect and the dry run easier to compare against the implementation.

Test the Boundary Cases and Failure Modes

Pointer algorithms often fail at the boundary, not in the middle. Test the cases that change the shape of the list.

Remove the head

For:

1 -> 2 -> 3
n = 3

The original head is the third node from the end.

After the initial gap and paired traversal:

trail = dummy
trail.next = 1

The mutation becomes:

dummy.next = dummy.next.next

The result is:

2 -> 3

This is the case that exposes unsafe head handling. Without a dummy node, trail would not have a real predecessor.

Remove the only node

For:

1
n = 1

The target is also the head and the tail.

The rewiring changes:

dummy.next = 1

to:

dummy.next = None

Returning dummy.next correctly produces an empty list.

Remove the tail

For:

1 -> 2 -> 3
n = 1

The trailing pointer stops at node 2:

2.next = 2.next.next

Since 2.next is node 3 and 3.next is None, the result is:

1 -> 2

Check a two-node list

Use both possible removals:

1 -> 2, n = 1  -> 1
1 -> 2, n = 2  -> 2

These small cases reveal whether the loop stops at the predecessor or one node too early or too late.

Common failures include:

• Advancing lead by n while using the dummy-based lead is None convention.
• Advancing by n + 1 but starting one pointer at head.
• Returning head instead of dummy.next, which fails when the original head is removed.
• Moving the pointers until lead.next is None when the chosen initialization expects lead is None.
• Dereferencing trail.next or lead.next after the wrong loop has already moved a pointer beyond the valid state.
• Mutating links before proving that trail is at the predecessor.

A passing trace for the middle case is not enough. The head-removal and singleton cases test whether the algorithm's structure is actually uniform.

Complexity and the Transferable Recognition Rule

The lead pointer traverses the list once during the initial gap and paired scan. The trailing pointer also moves forward, but neither pointer retreats or creates extra storage.

Therefore:

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

The practical distinction from the baseline is that the list is processed in one forward scan rather than counted and then scanned again. The dummy node also removes a special-case branch from the deletion logic.

The reusable decision rule is:

When a singly linked list asks for a position relative to the end, convert that position into a fixed forward gap. If deletion needs the predecessor, add a dummy node so head removal follows the same rule as every other removal.

Before coding, say these five details out loud:

1. Where do both pointers start?
2. How many links does the lead pointer advance?
3. What condition ends the paired traversal?
4. Which pointer is the predecessor at termination?
5. Which pointer represents the returned head?

For this convention, the answers are:

Both start at dummy.
Lead advances n + 1 links.
The loop ends when lead is None.
Trail is the predecessor.
Return dummy.next.

That is the whole mechanism. Dry-run n = 1, then dry-run n = length. If both traces land on the correct predecessor, implement from the invariant rather than copying pointer names. A fixed gap turns an end-relative question into a local pointer rewrite.