19. Remove Nth Node From End of List - Detailed Explanation

Problem Statement

Description:
Given a singly linked list, remove the nth node from the end of the list and return its head. You are guaranteed that n is valid, meaning that the linked list contains at least n nodes.

Examples:

1. Example 1:

   • Input: head = [1, 2, 3, 4, 5], n = 2
   • Output: [1, 2, 3, 5]
   • Explanation: The second node from the end is the node with value 4. Removing it results in the list [1, 2, 3, 5].

2. Example 2:

   • Input: head = [1], n = 1
   • Output: []
   • Explanation: Removing the only node in the list yields an empty list.

3. Example 3:

   • Input: head = [1, 2], n = 1
   • Output: [1]
   • Explanation: Removing the last node (node with value 2) results in the list [1].

Constraints:

• The number of nodes in the list is between 1 and 30.
• 1 ≤ n ≤ number of nodes in the list.

Hints Before the Solution

1. Two-Pointer Technique:
   Use a fast pointer and a slow pointer. Move the fast pointer n steps ahead of the slow pointer so that when the fast pointer reaches the end, the slow pointer is right before the node you need to remove.

2. Dummy Node:
   To simplify edge cases (like removing the head of the list), create a dummy node that points to the head. This ensures that every node has a previous node.

Approaches

Approach 1: Two-Pass Solution

Idea:

• First Pass: Traverse the linked list to count the total number of nodes.
• Second Pass: Compute the position of the node to remove from the start (which is totalNodes - n) and traverse again to that position, then adjust the pointers to remove the target node.

Pros:

• Easy to understand and implement.

Cons:

• Requires two traversals of the linked list.

Approach 2: Optimal One-Pass Solution Using Two Pointers

Idea:

• Initialization: Create a dummy node pointing to the head. Set two pointers, fast and slow, both starting at the dummy.

• Advance Fast Pointer: Move the fast pointer n+1 steps forward. This ensures that the gap between fast and slow is n nodes.

• Simultaneous Movement: Move both pointers one step at a time until the fast pointer reaches the end. At that point, the slow pointer will be just before the node that needs to be removed.

• Remove Node: Adjust slow.next to skip the target node.

Pros:

• Only one pass through the list is needed.
• Handles edge cases smoothly with the dummy node.

Cons:

• Requires careful pointer management.

Code Implementations

Python Implementation