Remove Nth Node From End of List

Problem Link - https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

Linked Lists become much more interesting when the problem asks us to work from the end of the list while only having access to the head.

Today's problem is a classic interview favorite because it tests:

• Linked List traversal


• Two Pointer technique


• Edge case handling


• Space optimization

Let's break it down.

Problem Statement

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

Example

Input:

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

n = 2



Output:

[1,2,3,5]

The 2nd node from the end is 4, so we remove it.

Brute Force Approach

The straightforward idea is:

1. Traverse the entire list and calculate its length.


2. Find the position of the node to delete from the beginning.


3. Traverse again to the previous node.


4. Update pointers and remove the target node.

Interview-Oriented Explanation

Since the node to remove is given from the end, we can first determine the total length of the list. Once we know the length, we can convert the problem into deleting a node from a known position from the start. This requires two traversals of the linked list.

Time & Space Complexity

• Time Complexity: O(N)
  


• Space Complexity: O(1)
  

Java Solution

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {



        int len = 0;

        ListNode cur = head;



        while (cur != null) {

            len++;

            cur = cur.next;

        }



        if (len == n) {

            return head.next;

        }



        cur = head;



        for (int i = 1; i < len - n; i++) {

            cur = cur.next;

        }



        cur.next = cur.next.next;



        return head;

    }

}

Shifting Towards the Optimal Approach

The brute force solution traverses the list twice.

Can we identify the node to delete without calculating the length first?

Yes.

If we maintain a gap of exactly n nodes between two pointers, then when the fast pointer reaches the end, the slow pointer will automatically stand just before the node that needs to be removed.

This observation leads us to the famous Fast & Slow Pointer Technique.

Optimal Approach (Two Pointers)

Intuition

1. Create a dummy node before the head.


2. Move the fast pointer n steps ahead.


3. Move both pointers together.


4. When fast reaches the last node, slow will be just before the node to delete.


5. Remove the node and return the list.

The dummy node helps us handle the edge case where the head itself needs to be removed.

Dry Run

Input

1 -> 2 -> 3 -> 4 -> 5

n = 2

Step 1

Move fast pointer 2 steps ahead.

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

slow

             fast

Step 2

Move both pointers together.

slow -> 1, fast -> 3

slow -> 2, fast -> 4

slow -> 3, fast -> 5

Now:

fast.next == null

So stop.

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

                    slow

                         fast

Step 3

Delete the next node of slow.

slow.next = slow.next.next;

Result:

1 -> 2 -> 3 -> 5

Optimal Java Solution

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {



        ListNode dummy = new ListNode(0);

        dummy.next = head;



        ListNode slow = dummy;

        ListNode fast = dummy;



        for (int i = 0; i < n; i++) {

            fast = fast.next;

        }



        while (fast.next != null) {

            slow = slow.next;

            fast = fast.next;

        }



        slow.next = slow.next.next;



        return dummy.next;

    }

}

Complexity Analysis

Key Interview Takeaway

The trick is not finding the length of the linked list.

The real insight is maintaining a fixed gap of n nodes between two pointers. When the fast pointer reaches the end, the slow pointer naturally reaches the exact position needed to perform the deletion.

This fixed-gap technique is one of the most important Linked List patterns and appears in many interview problems.