Remove Nth Node From End of List – 19. LeetCode

The “Remove Nth Node From End of List” problem asks you to remove the nth node from the end of a singly linked list. Think of it as counting backwards in a list of items and removing the specific one you’re pointing at. This involves understanding how to traverse and manipulate the linked list efficiently.

Brute Force

public class RemoveNthNodeBruteForce {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = 0;
        ListNode current = head;

        // Step 1: Count the total number of nodes
        while (current != null) {
            length++;
            current = current.next;
        }

        // Step 2: Find the node just before the one to remove
        int targetIndex = length - n;
        current = dummy;
        for (int i = 0; i < targetIndex; i++) {
            current = current.next;
        }

        // Step 3: Remove the nth node
        current.next = current.next.next;

        return dummy.next;
    }
}

1. Traverse the entire list to calculate its length.

2. Calculate the position of the node to be removed from the start (length – n).

3. Traverse the list again up to that position and adjust pointers to skip the nth node.

4. Use a dummy node to simplify edge cases (like removing the head).

This approach is simple but requires two traversals, making it less efficient.

Optimal Approach: Two-Pointer Technique

Algorithm and Data Structure Pattern Used:

• Two-pointer technique: This is a common algorithmic strategy to solve problems involving linked lists in a single traversal.

• Linked list: The core data structure used here, where nodes are connected via pointers.

To remove the nth node from the end in one traversal, we can maintain two pointers:

1. First pointer starts at the head and moves n + 1 steps forward.

2. Second pointer starts at the head and only begins moving after the first pointer has reached its position.

3. Once the first pointer reaches the end of the list, the second pointer will be right before the node to remove. This ensures we don’t need to traverse the list twice.

Algorithm Steps

1. Create a dummy node and link it to the head of the list to handle edge cases like removing the head node.

2. Initialize two pointers, both starting at the dummy node.

3. Move the first pointer n + 1 steps forward.

4. Move both pointers one step at a time until the first pointer reaches the end of the list.

5. The second pointer will now point to the node just before the nth node from the end. Adjust its next pointer to skip the nth node.

6. Return the new head of the list.

public class RemoveNthNode {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Create a dummy node to simplify edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        
        // Move fast pointer n + 1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // Move both pointers until fast reaches the end
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // Skip the target node
        slow.next = slow.next.next;
        
        return dummy.next; // Return the updated list
    }
}

Line By Line Explanation

1. Dummy Node Creation

ListNode dummy = new ListNode(0);
dummy.next = head;

• Creates a new node (dummy) with value 0, and sets its next pointer to the head of the list.
• Dummy node simplifies edge cases, such as when the head itself is removed. It ensures there is always a node before the one being deleted.
• Using a dummy node is a common technique to handle edge cases cleanly without additional condition checks.

2. Initialize Pointers

ListNode fast = dummy, slow = dummy;

• Initializes two pointers, fast and slow, both pointing to the dummy node.
• The two-pointer approach allows traversal of the list in a single pass. The fast pointer will help maintain a gap of n nodes between itself and the slow pointer.

3. Advance the fast Pointer

for (int i = 0; i <= n; i++) {
    fast = fast.next;
}

• Moves the fast pointer n + 1 steps ahead of the slow pointer.
• Thus step ensures that the algorithm works in one pass by maintaining the correct gap between the pointers, a hallmark of efficient linked list traversal.

4. Traverse the List with Two Pointers

while (fast != null) {
    fast = fast.next;
    slow = slow.next;
}

• Efficiently moves through the list while adhering to the single-pass constraint.

5. Remove the Target Node

slow.next = slow.next.next;

• This is the critical step where the node is removed from the list by bypassing it.

6. Return

return dummy.next;

• Returning the head of the modified list maintains clarity and simplicity for the caller.

Why This Code Works

This solution leverages the two-pointer technique to efficiently find and remove the nth node from the end of the list in a single pass. The use of a dummy node simplifies edge-case handling, while direct pointer manipulation ensures optimal space usage. The code is clean, efficient, and adheres to best practices, making it suitable for interviews and competitive programming.