Remove Nth Node From End of List (LeetCode 19): The Optimized One-Pass Solution

In our previous article, we learned how to find the Nth node from the back. But in technical interviews at companies like Amazon, Google, or TCS, the question usually goes a step further: “How do you remove it?”

Since a Singly Linked List is a one-way street, you can’t simply jump to the end and walk backward. You have two choices:

1. The “Slow” Way: Traverse once to find the length (L), then traverse again to the (L-N) position.

2. The “Pro” Way (One-Pass): Use the “Gap” logic with two pointers to find and delete the node in a single trip.

The Intuition: The “Fixed Gap” Strategy

Imagine you and a friend are running a race. If your friend starts running and gets a 10-meter head start, and then you both run at the exact same speed, the distance between you will always remain 10 meters.

When your friend hits the finish line, you will be exactly 10 meters behind them. This is how we pinpoint the target node without knowing the list’s total length.

• The Lead: Move the Fast pointer N steps ahead.

• The Sync: Start the Slow pointer from a “Dummy” node and move both at the same speed.

• The Target: When Fast reaches the end (None), Slow will be standing one node before the target. This is the perfect spot to “snip” the connection!

Python Code Implementation (LeetCode 19)

This approach is clean, memory-efficient, and handles the tricky “edge case” where you have to remove the head of the list.

def removeNthFromEnd(head, n):
    # Create a dummy node to handle edge cases (like removing the head)
    dummy = ListNode(0)
    dummy.next = head
    slow = fast = dummy

    # Step 1: Move 'fast' N+1 steps ahead to create the gap
    for i in range(n + 1):
        fast = fast.next

    # Step 2: Move both pointers until 'fast' hits the end
    while fast is not None:
        slow = slow.next
        fast = fast.next

    # Step 3: Delete the node (Skip the Nth node)
    slow.next = slow.next.next

    return dummy.next

The Tabular Dry Run

Let’s visualize deleting the 2nd node from the end (N=2) in a 5-node list.

List: 10 -> 20 -> 30 -> 40 -> 50 -> NULL

Phase 1: Creating the Gap

Phase 2: Moving in Sync

Final Result: slow is at 30. The target to remove was 40. By setting 30.next = 30.next.next, we skip 40 and connect 30 directly to 50. Mission accomplished!

Why This is a “One-Pass” Miracle

1. No Length Calculation: We never had to count the nodes.

2. Efficiency: We reached the answer as soon as the fast pointer “smelled” the end of the list.

3. Edge Case Safety: By using a Dummy Node, we avoid errors if N equals the total length of the list (deleting the head).

Key Takeaways for Students

• Time Complexity: O(n). We visit each node only once.

• Space Complexity: O(1). We only use a few extra pointer variables.

• Interview Tip: Always mention the “Dummy Node” approach to your interviewer; it shows you understand how to handle null pointer exceptions and head deletions.

Get the Full Source Code & Practice

I have uploaded the complete practice script to GitHub. This includes helper functions to test with different values of N so you can see the deletion in action.

👉 [Access the Practice Code on GitHub]

Frequently Asked Questions (FAQs)

1. Why use a Dummy Node?

If you need to remove the first node (the head), your slow pointer needs to be at a position before the head. A dummy node acts as that “before” position.

2. Is there a recursive solution?

Yes, you can use recursion to count from the bottom of the stack, but it uses O(n) space. The Two-Pointer method is superior for memory efficiency.

3. What if N is greater than the list length?

In real-world applications, you should add a check to see if the fast pointer becomes None before completing the initial N steps to avoid crashes.

If you really want to master Linked Lists, don’t just solve problems — build something real.

👉 I’ve created a complete DSA Project – Expense Tracker using only:

• Singly Linked List
• Basic operations (insert, delete, reverse, traversal)

🔗 [Click here to explore the full project]

This will help you:

• Understand real-world use cases
• Strengthen DSA concepts
• Prepare for interviews + projects

Happy Coding! Join the conversation on Study Trigger for more simplified DSA tutorials.