Remove Nth Node From End of List

How it works

Use two pointers so that the gap between them is exactly n. Move the right pointer n steps ahead first. Then move both pointers together. When the right pointer reaches the end, the left pointer will be just before the node we must remove. This avoids a separate length-counting pass, while still traversing the list in O(N) time. The key benefit is that the n-node gap tells us where to delete without storing nodes or computing the length first.

Steps

1. Create a dummy node pointing to the head (helps handle deletion of the first node).
2. Set two pointers:
   • left at dummy
   • right at head
3. Move right forward n steps.
4. Move both pointers until right reaches the end.
5. Now left.next is the node to delete → skip it by doing left.next = left.next.next.
6. Return dummy.next as the updated head.

Complexity

• Time complexity: O(N)
• Space complexity: O(1)

Things to watch for

Forgetting to Handle Head Removal

When n equals the length of the list, the head node itself must be removed. Without a dummy node or explicit check for this case, the code may crash or return incorrect results. Always verify your solution works when the target is the first node.

Off-by-One Errors in Pointer Positioning

The two-pointer technique requires the left pointer to stop at the node before the one to delete. A common mistake is advancing right by n-1 instead of n steps, causing the wrong node to be removed. Carefully trace through a small example to confirm your gap is correct.

Not Returning the Updated Head

After modifying the list, forgetting to return dummy.next (or the updated head) results in returning a stale reference. This is especially problematic when the original head was deleted. Always ensure your return statement reflects any structural changes to the list.

from typing import Optional

# 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(0, head)
        left = dummy
        right = head

        while n > 0:
            right = right.next
            n -= 1

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

        left.next = left.next.next
        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

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

        while (n > 0) {
            right = right->next;
            n--;
        }

        while (right != nullptr) {
            left = left->next;
            right = right->next;
        }

        left->next = left->next->next;
        return dummy->next;
    }
};