Remove Nth Node from End of Linked List

The remove nth node from end problem requires removing a specific node from a singly linked list when only given the position from the end. This classic algorithm demonstrates the power of the two-pointer technique for efficient linked list manipulation.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size range of the linked list? (e.g., 1 to 10^5 nodes)
2. Are duplicates allowed in the list?
3. Should I return the modified head node or mutate the original list?
4. Can I modify the input list in-place, or do I need to return a new list?
5. What is the target time complexity for the follow-up? (e.g., O(n) with single pass)

Restatement of the pattern: The "Remove nth node from end" problem involves removing a specific node from a singly linked list when only given the position from the end (1-indexed). This requires identifying the target node and adjusting pointers to exclude it from the list.

Signal words and constraint shape:

• "nth from end" or "remove the nth node from the end"
• Singly linked list (no backward traversal)
• Single pass requirement hints at two-pointer technique
• "1-indexed" or "0-indexed" position specification

Assumptions made:

• The input is a valid singly linked list with at least one node
• n is always valid (1 ≤ n ≤ size of list)
• The list has no cycles
• We can modify the input structure in-place

Scenario fit: This pattern is best suited for static scenarios where the entire list is available upfront and we need to perform a single modification. It's not ideal for streaming data where nodes arrive dynamically, as we'd need to know the list size beforehand or use more complex buffering approaches.

The core insight is that we can solve this in one pass using the two-pointer (fast/slow) technique, maintaining a fixed distance between pointers to locate the target node efficiently.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Remove the nth node from the end" or "delete the Nth element from the end"
• References to linked list structures (often with "head" pointer)
• Problems asking for removal based on position from the end rather than beginning
• "nth from the end" or "kth from the end" phrasing

Why this pattern fits better than alternatives: This is fundamentally a two-pointer (sliding window) problem that leverages the relationship between position from end and position from beginning. It's more efficient than calculating list length first, then traversing to the target node (which would be O(2n) = O(n)), or using stack-based approaches (O(n) space). The two-pointer technique achieves O(n) time and O(1) space in a single pass.

When variations apply:

• If we're removing from the beginning or middle, a simple single-pass approach with previous node tracking works
• If we're removing from the end but don't know the list length, this pattern is essential
• If we're doing multiple removals or need to maintain order for other operations, a different approach like using a dummy node with two pointers becomes more appropriate

Core insight: The key insight is that we can use the relationship length - n to find the target node's position from the beginning, but we don't need to calculate the full length. By maintaining a fixed-distance gap between two pointers, we can find the target node in one traversal.

This pattern is particularly effective for linked list problems where position-based removals from the end are required, and it's a canonical example of how to use the "fast-slow pointer" or "two-pointer" technique for efficient single-pass solutions.

3. Approach Evolution

Interview communication script:

My first instinct is to use a two-pass approach where I first count the total nodes and then remove the nth from end. But that's O(n²) because I'd need to traverse the list twice - once to count and once to find the target node. Let me think about how to optimize this.

I notice that if I use a two-pointer technique with a gap of n between them, I can solve this in one pass. When the fast pointer reaches the end, the slow pointer will be at the node just before the one to remove. This is a classic "sliding window" or "two-pointer" pattern where I maintain an invariant that the gap between my pointers is exactly n.

The key insight is to use a dummy head node to handle edge cases uniformly - particularly when removing the first node. If I don't use a dummy, I have to handle special cases where the head itself needs removal.

Let me trace through this approach:

1. Create a dummy node that points to the head
2. Move fast pointer n steps ahead
3. Move both pointers until fast reaches end
4. Remove the node after slow pointer

This approach reduces time complexity from O(n²) to O(n) and space remains O(1).

Brute-force approach and why it is not ideal:

The brute force approach would be to:

1. First pass: count total number of nodes in the list - O(n) time
2. Second pass: find the (count - n)th node from beginning and remove it - O(n) time

This is inefficient because:

• Requires two complete traversals of the list
• Involves extra counting logic that's unnecessary
• Doesn't leverage the relationship between nth node from end and position from beginning

Improved approach and the key optimization:

The key optimization is to use the two-pointer (sliding window) technique:

• Use a "fast" pointer that moves n steps ahead of the "slow" pointer
• When fast reaches the end, slow will be pointing to the node just before the target
• This allows us to find the target in a single pass without counting

The invariant maintained is that the distance between fast and slow pointers is always n nodes.

Final approach with step-by-step reasoning:

1. Create a dummy node that points to the head to simplify edge case handling
2. Initialize two pointers (fast and slow) both pointing to dummy node
3. Advance fast pointer n steps ahead so that the gap between pointers is exactly n
4. Move both pointers simultaneously until fast reaches the last node (null)
5. At this point, slow pointer is at the node just before the target to remove
6. Update the next reference of slow pointer to skip the target node

Important invariants that must hold:

• Fast and slow pointers maintain exactly n nodes between them throughout traversal
• Dummy node ensures consistent handling of edge cases like removing the first element

Alternative approach considerations:

While we could use a stack to store all nodes and then pop n times, that would require O(n) space. The two-pointer approach is superior because it's O(1) space and O(n) time with clean, readable logic.

The sliding window pattern is perfect here because we're looking for a specific relative position in the list, and the gap between our two pointers directly maps to that relationship.

4. Data Structure Choice

For the "Remove nth node from end" problem, the primary data structure is a singly linked list with nodes containing an integer value and a pointer to the next node.

Primary Data Structures Used

Linked List Node:

• ListNode class with val and next fields
• Required to represent the input structure
• Space complexity: O(n) where n is the number of nodes

Why Each Data Structure Is Needed

The ListNode structure is essential because:

1. It represents the actual input data structure (linked list)
2. It enables traversal and modification operations
3. It provides the necessary pointers to connect nodes in sequence

Time and Space Impact

Time Complexity:

• All operations (traversal, deletion) are O(n) where n is the list length
• Single pass through the list for most approaches

Space Complexity:

• O(1) extra space for two-pointer approach (most efficient)
• O(n) space for stack-based approaches
• O(1) auxiliary space for the linked list itself (not counting input)

Helper Structures

No additional helper structures are needed for the optimal two-pointer approach. The solution uses only a dummy node to simplify edge case handling (when removing the head node) and maintains two pointers (fast and slow) to track positions.

The dummy node approach is preferred over maintaining separate head tracking because it eliminates special case handling for removing the first node, making the code cleaner and more maintainable.

5. Algorithm Walkthrough

Let me trace through the two-pointer approach on a concrete example to show how it works.

Example: head = [1,2,3,4,5], n = 2

Step-by-step execution:

1. Initialization:

   • fast = head (points to node 1)
   • slow = head (points to node 1)
   • fast is advanced by n=2 positions first

2. First advancement:

   • Move fast two steps: fast = 3, slow = 1
   • fast now points to node 3

3. Second advancement:

   • Move fast one more step: fast = 4, slow = 1
   • fast now points to node 4

4. Main loop:

   • While fast.next != null:
     • Move both pointers: fast = 5, slow = 2
   • Now fast points to node 5, which has no next node

5. Removal:

   • slow.next = slow.next.next → Remove node 4 (2's next points to 5)
   • Result: 1->2->3->5

Key insight: When fast reaches the end, slow is exactly at the node before the one to be removed.

Edge case handling:

• If fast becomes null after initial advancement, it means we need to remove the first node
• In that case, return head.next directly

The algorithm terminates correctly because we maintain the invariant that fast is always exactly n nodes ahead of slow, ensuring when fast reaches the end, slow points to the node just before the target.

graph LR
    A[1] --> B[2] --> C[3] --> D[4] --> E[5]
    A -->|slow| B
    C -->|fast| E
    
    style A fill:#f9f,stroke:#333
    style B fill:#fff,stroke:#333
    style C fill:#fff,stroke:#333
    style D fill:#fff,stroke:#333
    style E fill:#fff,stroke:#333

6. Java Solution

/**
 * 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) {
        // Create a dummy node to handle edge case of removing the first node
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // Use two pointers with n nodes between them
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // Move fast pointer n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        
        // Move both pointers until fast reaches the last node
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // Remove the nth node from end by skipping it
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

This solution uses the two-pointer technique (also known as the "fast and slow pointer" or "tortoise and hare" approach) to efficiently remove the nth node from the end of a linked list in a single pass. The dummy node handles edge cases where we need to remove the first node, making the logic uniform for all cases.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the linked list with two pointers moving at the same pace. Each node is visited exactly once, making the time complexity linear with respect to the number of nodes in the list.

Space Complexity: O(1)

The solution uses only a constant amount of extra space regardless of the input size. Only a few pointer variables (fast, slow, and temp) are used to track positions in the list. No additional data structures like arrays or hash maps are required, making the space complexity constant.

Why These Bounds Are Correct:

The linear time complexity is optimal for this problem because we must at minimum examine each node to determine its position in the list. Since we're removing a specific node, we must identify it by traversing the list once. The constant space complexity is achieved because we're not storing any intermediate results or creating additional data structures that scale with input size.

Optimality:

This solution is optimal in both time and space complexity. There's no way to solve this problem with better than O(n) time since we must traverse the list at least once to find the target node. Similarly, O(1) space is optimal since we only need a fixed number of pointers to track our position, and no additional storage is required for the algorithm to function correctly.

The solution achieves the theoretical lower bounds for this problem, making it both time and space optimal.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty list: When head is null, the method should return null without any operation
• Single node list: When head points to one node and n = 1, the result should be null (removing the only node)
• Two nodes: n = 1 removes the second node, n = 2 removes the first node

Duplicate Values and Repeated States

• The algorithm works regardless of duplicate values in nodes, since it operates on positional indices rather than value-based comparisons
• The same node removal logic applies whether values are unique or duplicated

Boundary Conditions

• n equals list length: When removing the first node (e.g., list of size 3 with n=3), the head pointer must be updated to point to the second node
• n exceeds list length: This should not happen per problem constraints, but if it did, it would cause an invalid index
• n = 0: This is not a valid input according to the problem definition but should be handled gracefully

Common Implementation Mistakes

• Not handling the head node removal: Failing to update head when removing the first node leads to a dangling reference or incorrect result
• Off-by-one errors in pointer traversal: Miscounting nodes when using two pointers or failing to account for the dummy node's position
• Incorrect null pointer handling: Not properly checking for null references when accessing next pointers or when the list is empty
• Failing to return the updated head: The method must return the new head of the list after modification, not just update the internal structure

Additional Considerations

• Integer overflow: If n were very large, it could cause issues with pointer arithmetic (though not a concern in typical constraints)
• Memory management: In languages with manual memory management, ensuring proper cleanup of removed nodes is important (not an issue in Java's garbage collection)

9. Alternative Approaches

There are several alternative approaches to solving the "Remove Nth Node from End" problem, each with different trade-offs:

Two-Pass Approach:

• First pass: calculate the total length of the list
• Second pass: reach the (length - n)th node from beginning and remove it
• Time: O(n), Space: O(1)
• This is simpler to understand but requires two passes through the list

Stack-Based Approach:

• Push all nodes onto a stack, then pop n times to reach the target node
• Time: O(n), Space: O(n)
• More intuitive but uses extra space proportional to list size

Recursive Approach:

• Use recursion to traverse to the end, then count backward
• When we're n nodes from the end, remove the next node
• Time: O(n), Space: O(n) due to recursion stack
• Elegant but not optimal for space usage

Dummy Node + Two Pointers (Chosen Solution):

• Uses a single pass with two pointers maintaining n distance
• Time: O(n), Space: O(1)
• Most efficient in both time and space complexity

The chosen two-pointer approach is preferred because it's optimal in both time and space, requires only one pass, and doesn't rely on recursion or additional data structures that grow with input size. The stack-based approach is less efficient due to O(n) space usage, and the two-pass approach is less efficient due to requiring multiple traversals.

10. Test Cases

public class RemoveNthNodeFromEndTest {
    public void runTests() {
        // Test case 1: Basic case - remove middle element
        ListNode head1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode result1 = removeNthFromEnd(head1, 2);
        // Expected: [1,2,3,5]
        
        // Test case 2: Remove first element
        ListNode head2 = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode result2 = removeNthFromEnd(head2, 3);
        // Expected: [2,3]
        
        // Test case 3: Remove last element
        ListNode head3 = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode result3 = removeNthFromEnd(head3, 1);
        // Expected: [1,2]
        
        // Test case 4: Single element list
        ListNode head4 = new ListNode(1);
        ListNode result4 = removeNthFromEnd(head4, 1);
        // Expected: []
        
        // Test case 5: Remove from very long list
        ListNode head5 = buildList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        ListNode result5 = removeNthFromEnd(head5, 4);
        // Expected: [1,2,3,4,5,6,7,9,10]
        
        // Test case 6: k equals list length (remove first)
        ListNode head6 = new ListNode(1, new ListNode(2));
        ListNode result6 = removeNthFromEnd(head6, 2);
        // Expected: [2]
        
        // Test case 7: Empty list
        ListNode result7 = removeNthFromEnd(null, 1);
        // Expected: null
    }
    
    private ListNode buildList(int... values) {
        if (values.length == 0) return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }
}

The test cases cover:

1. Basic functionality - removing a middle node
2. Edge case: Remove first element - when k equals list length
3. Edge case: Remove last element - boundary condition
4. Minimal input - single node list
5. Large input - performance with longer lists
6. Empty input - null list handling

Each test validates the correct removal of the nth node from the end while maintaining proper list structure and handling all edge cases that could break the algorithm.

11. Final Summary

The core idea is to remove the nth node from the end of a linked list using a two-pointer technique that maintains a fixed-distance gap between pointers. This approach works efficiently by advancing one pointer n steps ahead, then moving both pointers together until the lead pointer reaches the end, ensuring the trailing pointer points to the node just before the target. The solution is optimal with O(n) time and O(1) space complexity, making it ideal for production systems where memory and performance are critical considerations.