Remove Nth Node From End DSA Solution

Learning Outcome

After this lesson, you should be able to remove a node from the end of a linked list using a one-pass pointer gap and a dummy node.

Problem Statement

Given the head of a linked list and an integer n, remove the nth node from the end of the list and return the head.

Input	n	Output
`1 -> 2 -> 3 -> 4 -> 5`	`2`	`1 -> 2 -> 3 -> 5`
`1`	`1`	`null`

Brute Force Approach

Count the length of the list, compute which node should be removed from the front, then walk again to unlink it.

This is correct, but it requires two passes.

Optimized Approach

Create a dummy node before the head. Move fast ahead by n + 1 steps from the dummy. Then move fast and slow together until fast reaches null. At that moment, slow.next is the node to remove.

Exact Pseudocode

dummy = new node before head
dummy.next = head
fast = dummy
slow = dummy
for step from 0 to n:
  fast = fast.next
while fast is not null:
  fast = fast.next
  slow = slow.next
slow.next = slow.next.next
return dummy.next

Reference Code

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        slow = dummy
        fast = dummy

        for _ in range(n + 1):
            fast = fast.next

        while fast:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next
        return dummy.next

Sample Dry Run

Phase	fast	slow	Meaning
Start at dummy	dummy	dummy	Dummy protects head removal
Move fast n+1 steps	3	dummy	Gap is set for `n = 2`
Move together	4 then 5 then null	1 then 2 then 3	Slow stops before node 4
Remove	null	3	Set `3.next = 5`

Complexity

Measure	Value	Reason
Time	O(n)	The list is traversed once after setting the gap.
Space	O(1)	Only pointers and one dummy node are used.

Edge Cases

Removing the head node.
Single-node list.
Removing the tail node.

Interview Checklist

Use a dummy node to handle removing the head.
Create a gap of n + 1 from dummy to fast.
Stop slow on the node before the one to remove.

FAQs

Why use a dummy node?

It makes head removal follow the same unlinking logic as every other removal.

Why move fast n + 1 steps?

That positions slow one node before the target when fast reaches the end.

What is the core pattern?

Two pointers with a fixed gap.

Remove Nth Node From End: Two pointers Pattern