Remove Nth Node From End of List

Problem Description

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

Examples

Constraints

• The number of nodes in the list is sz.
• 1 ≤ sz ≤ 30
• 0 ≤ Node.val ≤ 100
• 1 ≤ n ≤ sz

Create a Gap of n Between Two Pointers, Then Advance Together

To remove the nth node from the end, you need to stop one node before it. The two-pointer technique: advance right by n positions first. Then advance both left and right together. When right reaches null, left is exactly at the node before the one to remove. Skip that node with left.next = left.next.next.

A dummy head before the real head lets left start there, which handles removing the actual head node without any special casing.

Solution 1: Two Passes (Count Then Delete)

Count the length of the list, then calculate the position from the front and remove it.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // count list length
        int length = 0;
        ListNode curr = head;
        while (curr != null) { length++; curr = curr.next; }

        // position from front is (length - n); use dummy to handle removing head
        ListNode dummy = new ListNode(0, head);
        curr = dummy;
        for (int i = 0; i < length - n; i++) curr = curr.next;
        curr.next = curr.next.next;
        return dummy.next;
    }
}

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        dummy = ListNode(0, head)
        curr = dummy
        for _ in range(length - n):
            curr = curr.next
        curr.next = curr.next.next
        return dummy.next

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 0;
        ListNode* curr = head;
        while (curr) { length++; curr = curr->next; }

        ListNode dummy(0, head);
        curr = &dummy;
        for (int i = 0; i < length - n; i++) curr = curr->next;
        curr->next = curr->next->next;
        return dummy.next;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Two passes through the list.
• Space Complexity: O(1). Only pointer variables.

Where it breaks: two passes instead of one. Not a problem in practice, but the one-pass approach demonstrates a sharper understanding.

Solution 2: One Pass with Two Pointers

Advance right by n steps, creating a gap. Then advance both until right is null. Delete the node after left.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy, right = head;

        // advance right by n steps to create an n-node gap
        for (int i = 0; i < n; i++) right = right.next;

        // advance both until right falls off the end
        while (right != null) {
            left = left.next;
            right = right.next;
        }

        // left is now one node before the target
        left.next = left.next.next;
        return dummy.next;
    }
}

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        left, right = dummy, head

        # advance right by n steps to create an n-node gap
        for _ in range(n):
            right = right.next

        # advance both until right falls off the end
        while right:
            left = left.next
            right = right.next

        # left is now one node before the target
        left.next = left.next.next
        return dummy.next

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head);
        ListNode* left = &dummy, *right = head;

        // advance right by n steps to create an n-node gap
        for (int i = 0; i < n; i++) right = right->next;

        // advance both until right falls off the end
        while (right) {
            left = left->next;
            right = right->next;
        }

        // left is now one node before the target
        left->next = left->next->next;
        return dummy.next;
    }
};

Complexity Analysis:

• Time Complexity: O(sz). One pass through the list.
• Space Complexity: O(1). Dummy node and two pointers.

Where it breaks: if n == sz (removing the head), right reaches null after the initial n-step advance and the while loop never runs. left stays at dummy, and dummy.next = dummy.next.next correctly removes the head. The dummy head handles this without special casing.

Common Mistakes

• Not using a dummy head. When n == list length, you need to remove the head node. Without the dummy, left.next = left.next.next would require left to be some node before head, which doesn’t exist without the dummy.
• Starting right at dummy instead of head. If both start at dummy, you’d need to advance right by n + 1 steps instead of n. Starting right at head with n advances is more intuitive.
• Advancing right by n + 1 when it should be n. The gap should leave left one node before the target. Work through a small example on paper before coding.

Frequently Asked Questions

Why does starting left at dummy handle removing the head node? When n == sz, advancing right by n steps puts it at null (past the last node). The while loop doesn’t run. left stays at dummy. Then dummy.next = dummy.next.next removes the original head, and dummy.next is the new head. Without the dummy, there’s no node before head to set next on.

What if the list has only one node and n = 1? right = head.next = null after one advance. While loop skips. dummy.next = dummy.next.next = null. Returns dummy.next = null. Correct.

Is there a way to do this without a dummy node? Yes, but it requires separate handling for the case where the head is removed. The dummy node costs one extra allocation and saves the conditional branch. In an interview, always use the dummy.

← All Problems