Remove Nth Node from the End of the Linked List

1. Problem Statement & Overview

When working with singly linked lists, we often encounter problems where we need to traverse or modify nodes based on their position relative to the end of the list. Because a singly linked list only points forward (from head to tail via next pointers), we cannot simply walk backwards.

Given the head of a linked list and an integer n, the objective is to remove the $n^{\text{th}}$ node from the end of the list and return the modified list's head.

2. The Core Challenge of Backwards Counting

In an array or ArrayList, finding an element from the end is trivial because we can use direct index arithmetic: length - n.

In a singly linked list, however:

• We do not know the total length of the list beforehand.
• We cannot traverse backwards because nodes only store references to their succeeding neighbor (node.next), not their preceding neighbor.

Thus, we need algorithmic strategies to either compute the length first or locate the target node efficiently using pointers.

3. Approach 1: The Brute-Force Two-Pass Solution

The most intuitive brute-force approach involves calculating the exact length of the linked list first, and then performing a second traversal to locate the node right before the target.

Step-by-Navigating Walkthrough

1. Pass 1 (Length Calculation): Initialize a counter to 0 and a temporary pointer at the head. Traverse until temp hits null, incrementing counter at each step.
2. Determine Target Position: The node we want to delete is at position length - n from the 0-indexed start. More importantly, to safely delete a node in a singly linked list, we must stop at the previous node (length - n - 1 or adjusted for 1-based counting) so we can update its next pointer.
3. Pass 2 (Pointer Adjustment): Reset temp to the head and decrement our target index until we reach the node right before the target.
4. Link Modification: Bypass the target node by setting temp.next = temp.next.next.

Pseudo-Code Implementation

// Brute-force approach pseudo-code
int counter = 0;
Node temp = head;

// Pass 1: Compute length
while (temp != null) {
    counter++;
    temp = temp.next;
}

// Edge case: If n equals the total length, we are deleting the head
if (counter == n) {
    Node newHead = head.next;
    return newHead; // (Remember to free memory in C++ if applicable)
}

// Pass 2: Find (counter - n)th node (1-based index from start)
int stepsToMove = counter - n;
temp = head;
for (int i = 0; i < stepsToMove - 1; i++) {
    temp = temp.next;
}

// Re-link and delete
Node deleteNode = temp.next;
temp.next = temp.next.next;

4. Analyzing the Brute-Force Approach

While straightforward, the brute-force method requires scanning the linked list multiple times.

• Drawback: In the worst-case scenario (e.g., when $n = 1$), we traverse almost the entire list twice, resulting in roughly $2N$ operations. Interviewers will typically ask for a single-pass solution.

5. Core Mental Model: The Two-Pointer (Fast & Slow) Analogy

To reduce the traversal to a single pass, we can use a Two-Pointer technique consisting of a fast pointer and a slow pointer.

Real-Life Analogy: The Track Runners

Imagine two runners on a running track.

• You want the second runner (slow) to finish exactly $N$ steps behind the lead runner (fast) when the lead runner hits the finish line.
• Instead of measuring the track's total length first, you command the lead runner (fast) to run ahead by $N$ steps right at the starting line.
• Once fast has a head start of $N$ steps, both runners begin running forward at the exact same speed (one step at a time).
• When fast reaches the end of the track (i.e., fast.next == null), slow will automatically be positioned precisely at the node right before the target node to be deleted!

6. Step-by-Step Evolution of the Optimal Algorithm

Let's trace the optimal single-pass algorithm with an example.

• List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
• $n$: 2 (Delete 2nd node from the end, which is 4)

Step 1: Head Start for the Fast Pointer

Move the fast pointer $N$ steps forward from the head.

Initial:  fast & slow at 1
After 2 steps:
  slow at 1
  fast at 3

Step 2: Simultaneous Movement

Move both fast and slow one step at a time until fast.next reaches null.

Step 3: Precise Positioning

Notice where slow is standing: it is pointing at node 3, which is right before the target node 4.

Step 4: Re-linking and Deletion

Node deleteNode = slow.next; // node 4
slow.next = slow.next.next;  // 3 now points to 5
// Free deleteNode memory if using C++

7. Handling Edge Cases

In linked list problems, edge cases often involve operations on the head node.

• Edge Case: What if $n$ is equal to the total length of the list (e.g., $N = 5$ in a 5-node list)?
• Behavior: The fast pointer will travel 5 steps and reach null right during the initial head-start phase.
• Solution: Check if fast == null after the initial head start. If it is, the node to delete is the head itself. Simply return head.next.

// Handling head deletion when fast reaches null during head start
if (fast == null) {
    return head.next;
}

8. Optimal Pseudo-Code Implementation

Below is the complete, production-ready logic for the optimal single-pass approach:

public Node removeNthFromEnd(Node head, int n) {
    Node fast = head;
    Node slow = head;
    
    // Step 1: Give fast pointer an n-step head start
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    // Edge case: If fast is null, n equals the length of the list (delete head)
    if (fast == null) {
        return head.next;
    }
    
    // Step 2: Move both fast and slow until fast reaches the last node
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    
    // Step 3: Bypass the target node
    Node deleteNode = slow.next;
    slow.next = slow.next.next;
    
    return head;
}

9. Complexity Analysis of the Optimal Approach

10. Summary and Key Takeaways

• The Limitation of Singly Linked Lists: Because nodes only contain forward references (next), backward traversal is impossible without extra logic or pointer manipulation.
• Brute-Force vs. Optimal: The brute-force method requires two passes (one to find length, one to locate the node), taking $O(2N)$ time. The optimal method uses a single pass with two pointers.
• The Fast & Slow Mental Model: Giving the fast pointer an $N$-step head start allows the slow pointer to land precisely on the node preceding the target when fast hits the end of the list.
• Memory Management in C++ vs. Java: In C++, you must explicitly free/delete removed nodes to prevent memory leaks, whereas languages like Java rely on garbage collection.
• Crucial Edge Case: Always account for the scenario where $N$ equals the total length of the list, which requires deleting and returning head.next.