Problem Description

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

Example 1

Input: head = [1, 2, 3, 4], n = 2
Output: [1, 2, 4]

The second node from the end is 3, so we remove it.

Example 2

Input: head = [5], n = 1
Output: []

The linked list contains only one node. Removing it results in an empty list.

Example 3

Input: head = [1, 2], n = 2
Output: [2]

The second node from the end is the first node, so the new head becomes 2.

Constraints

1 <= number of nodes <= 30
0 <= Node.val <= 100
1 <= n <= number of nodes

Approach: Two Pointers and a Dummy Node

A straightforward solution would be to calculate the length of the linked list first and then traverse it again to find the node that must be removed.

However, we can solve the problem in a single traversal using two pointers.

The main idea is:

1. Create a dummy node before the head.
2. Use two pointers, left and right.
3. Move the right pointer n steps ahead.
4. Move both pointers together until right reaches the end.
5. At that point, left will be positioned immediately before the node that must be removed.
6. Skip the target node by updating the next pointer.

Why Use a Dummy Node?

Removing the head node is a special case.

For example:

head = [1, 2]
n = 2

The node that must be removed is the head itself.

By adding a dummy node before the head, every node—including the original head—has a previous node. This allows us to use the same removal logic for all cases.

The list temporarily looks like this:

dummy -> 1 -> 2

After removing 1, we return dummy.next, which points to 2.

Python Solution

# Definition for singly-linked list.
# 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]:

        dummy = ListNode()
        dummy.next = head

        left = dummy
        right = head

        for _ in range(n):
            right = right.next

        while right:
            left = left.next
            right = right.next

        left.next = left.next.next

        return dummy.next

Step-by-Step Explanation

Consider the following input:

head = [1, 2, 3, 4]
n = 2

The linked list with the dummy node becomes:

dummy -> 1 -> 2 -> 3 -> 4

Initially:

left = dummy
right = 1

Step 1: Move right Ahead by n Positions

Since n = 2, move right two times:

First move:  right = 2
Second move: right = 3

Now there is a gap of two nodes between the positions represented by the two pointers.

Step 2: Move Both Pointers Together

Move both pointers until right becomes None.

left = 1, right = 4
left = 2, right = None

When right reaches the end, left is positioned immediately before the node that must be removed.

The target node is:

left.next = 3

Step 3: Remove the Target Node

We skip node 3 using:

left.next = left.next.next

Before removal:

2 -> 3 -> 4

After removal:

2 -> 4

The final linked list is:

[1, 2, 4]

Understanding the Pointer Gap

The right pointer starts n nodes ahead of the left pointer.

Because both pointers move at the same speed, this gap remains unchanged.

When right reaches the end of the linked list, left.next points to the nth node from the end.

This allows us to locate the target node without calculating the total length of the list.

Complexity Analysis

Time Complexity

O(sz)

Although the solution contains a for loop and a while loop, the pointers collectively traverse the linked list only a constant number of times.

Space Complexity

O(1)

The solution uses only a dummy node and two pointers. No additional data structure grows with the size of the linked list.

Key Takeaways

The two-pointer technique is useful when a problem asks us to find a node relative to the end of a linked list.

The dummy node simplifies edge cases, especially when the node being removed is the head.

By maintaining a gap of n nodes between the pointers, we can remove the nth node from the end in one pass with constant extra space.