1. First Pass: Traverse the entire linked list starting from the head to count the total number of nodes, denoted as $L$.
2. Calculate Target: The node to remove is located at the index $L - n$ (0-indexed). The node before the target (the predecessor) is at index $L - n - 1$.
3. Second Pass: Traverse the list again from the head, stopping at the $(L - n - 1)$-th node.
4. Removal: Update the next pointer of the predecessor to skip the target node.

Pseudo-code:

text
function removeNthFromEnd(head, n):
    length = 0
    current = head
    while current is not null:
        length++
        current = current.next
        
    targetIndex = length - n
    if targetIndex == 0: return head.next
    
    current = head
    for i from 0 to targetIndex - 1:
        current = current.next
        
    current.next = current.next.next
    return head

Why it is suboptimal: While the time complexity is $O(L)$ and space is $O(1)$, this approach requires traversing the list twice (specifically $2L - n$ steps). The problem statement includes a follow-up asking for a one-pass solution. In high-performance scenarios or interviews, reducing the number of traversals demonstrates a deeper understanding of pointer manipulation.

Core Insight for Remove Nth Node From End of List

The core intuition behind the optimal LeetCode 19 solution is to create a "window" or "gap" of size $n$ between two pointers, fast and slow.

If we advance the fast pointer so that it is $n$ steps ahead of the slow pointer, the two pointers maintain this fixed distance as they move. When the fast pointer reaches the end of the list (null), the slow pointer will be exactly $n$ nodes away from the end.

To delete a node in a singly linked list, we need access to its predecessor (the node immediately before it). Therefore, we adjust the gap slightly: we ensure the fast pointer is $n + 1$ steps ahead of the slow pointer.

Visual Description: Imagine two pointers moving along the list. Initially, both start at a dummy node placed before the head. The fast pointer moves forward $n + 1$ times, creating the gap. Then, both pointers move one step at a time simultaneously. As fast falls off the end of the list (reaches null), slow lands exactly on the node before the one we want to remove. This allows us to perform the deletion operation slow.next = slow.next.next immediately.

Execution Flow

Let's trace the algorithm with Input: head = [1, 2, 3, 4, 5], n = 2.

1. Setup:

   • Create dummy node with val=0, next=head.
   • List: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null.
   • slow points to dummy.
   • fast points to dummy.

2. Create Gap:

   • Move fast $n + 1$ (which is 3) steps.
   • Step 1: fast at 1.
   • Step 2: fast at 2.
   • Step 3: fast at 3.
   • Current state: slow at dummy, fast at 3. Gap is established.

3. Slide Window:

   • Loop condition: fast is not null.
   • Iteration 1:
     • slow moves to 1.
     • fast moves to 4.
   • Iteration 2:
     • slow moves to 2.
     • fast moves to 5.
   • Iteration 3:
     • slow moves to 3.
     • fast moves to .

4. Deletion:

   • slow is at node 3. The target to remove is slow.next (node 4).
   • Operation: slow.next = slow.next.next (points 3 to 5).
   • List becomes: dummy -> 1 -> 2 -> 3 -> 5 -> null.

5. Return:

   • Return dummy.next (node 1).

Proof of Correctness

Let $L$ be the length of the list. The nodes are indexed $0$ to $L-1$. The $n$-th node from the end corresponds to the index $L - n$. The predecessor of this node is at index $L - n - 1$.

We start with a dummy node at index $-1$.

1. We advance fast by $n + 1$ steps. fast is now at index $n - 1$ (relative to the original list, or $n$ steps from dummy).
2. The distance from fast to the end (null, effectively index $L$) is $L - (n - 1) = L - n + 1$ steps? No, simpler: fast starts at dummy. After $n+1$ steps, fast is at the $n$-th node of the list.
3. Let $k$ be the number of steps fast takes to reach null from its current position.
4. slow also takes $k$ steps from the dummy node.
5. When fast reaches null, it has traversed a total of $L + 1$ nodes (including dummy).
6. slow is $n + 1$ steps behind fast.
7. Therefore, slow's position is $(L + 1) - (n + 1) = L - n$ steps from the start (including dummy).
8. In terms of list indices (0-indexed), slow lands on index $L - n - 1$, which is exactly the predecessor of the target node at $L - n$.

Reference Implementation

C++ Solution for LeetCode 19

cpp
/**
 * 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) {
        // Use a dummy node to handle edge cases like removing the head
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        
        // Advance fast pointer so that the gap between fast and slow is n nodes
        // We move n + 1 times to land slow on the predecessor of the target
        for (int i = 0; i <= n; ++i) {
            fast = fast->next;
        }
        
        // Move both pointers until fast reaches the end
        while (fast != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }
        
        // Remove the nth node from the end
        ListNode* nodeToDelete = slow->next;
        slow->next = slow->next->next;
        delete nodeToDelete; // Good practice in C++ to free memory
        
        ListNode* newHead = dummy->next;
        delete dummy; // Clean up dummy node
        return newHead;
    }
};

Java Solution for LeetCode 19

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Dummy node simplifies edge cases (e.g., removing the only node)
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode slow = dummy;
        ListNode fast = 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) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Skip the desired node
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

Python Solution for LeetCode 19

python
# 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]:
        # Initialize dummy node pointing to head
        dummy = ListNode(0, head)
        slow = dummy
        fast = dummy
        
        # Move fast pointer n + 1 steps forward
        # This ensures slow stops at the node BEFORE the one we want to delete
        for _ in range(n + 1):
            fast = fast.next
            
        # Move both pointers until fast reaches the end
        while fast:
            slow = slow.next
            fast = fast.next
            
        # Delete the target node
        slow.next = slow.next.next
        
        return dummy.next

Q: Why does my solution fail on a single-node list?

• Mistake: Failing to handle the case where the list becomes empty.
• Why: If the list is [1] and n=1, the result should be []. If the logic assumes head is always returned, it might return [1] or crash.
• Consequence: Incorrect return value for small inputs. The dummy node strategy naturally handles this by returning dummy.next, which would be null.