Remove Nth Node From End of List Java Solution

This solution addresses the classic linked list problem of removing the nth node from the end of a list, demonstrating efficient two-pointer technique with dummy node optimization for clean edge case handling.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the maximum size of the linked list? (This helps determine if we need to consider memory constraints)
2. Can we modify the input list in-place, or do we need to return a new list?
3. Are there any constraints on the value of n (e.g., n is always valid, or do we need to handle invalid n values)?
4. Should we handle edge cases like removing the first node or a single-node list?
5. What is the expected time complexity for the solution? (e.g., O(n) or better)

Restatement in my own words: Given a singly linked list and an integer n, remove the nth node from the end of the list and return the head of the modified list.

Clarify inputs, outputs, and constraints:

• Input: Head node of a singly linked list (ListNode), integer n (1-indexed position from end)
• Output: Head node of the modified linked list after removing nth node from end
• Constraints:
  • Number of nodes in the list is between 1 and 30
  • Each node's value is between 0 and 100
  • n is always valid (1 ≤ n ≤ size of list)

Assumptions I'm making:

• The linked list is singly-linked (no previous pointers)
• We can modify the input list in-place
• The nth node from end means we count backwards from the last node (e.g., n=1 removes the last node, n=2 removes second-to-last)

Data shape and hidden structure:

• Linear data structure with pointer-based navigation
• The key insight is that we need to find the (length - n)th node from beginning to remove it
• This suggests we might benefit from a two-pointer technique or calculating length first

The problem has a clear linear structure where we're essentially removing one element from a sequence, but the challenge lies in efficiently identifying which element to remove without multiple passes through the list.

2. Pattern Recognition

The most likely pattern here is the Two Pointers (Fast and Slow) technique, also known as the "Floyd's Cycle Detection" approach adapted for linked list problems.

The wording that signals this pattern includes:

• "Remove Nth node from end" - This immediately suggests we need to traverse the list in a way that relates the position from the end to a position from the beginning
• The constraint of removing exactly one node - This suggests we can do it in a single pass through the list

This problem fits that pattern because:

1. We're dealing with a singly linked list where we can only traverse forward
2. The task requires us to find a specific node based on its position from the end
3. We can use two pointers at different speeds to effectively "count" from the end while maintaining a reference to the target node

The core insight is that we can use two pointers where one pointer advances n+1 steps ahead of the other, so when the fast pointer reaches the end, the slow pointer will be pointing to the node just before the one we need to remove.

This approach transforms a two-pass solution (find length, then find target) into a single-pass O(n) solution with O(1) space complexity.

The key realization is that we don't need to know the absolute position of the target node - we just need to position our slow pointer such that it points to the node before the one to be removed, allowing us to easily unlink it.

3. Approach Evolution

My first instinct is to use a two-pass approach where I first calculate the length of the list, then find the nth node from the end and remove it. But that's O(n²) because we need to traverse the list twice - once to get length, once to find removal point. 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.

Let me think about this more carefully. If I have a gap of n between two pointers, and the fast pointer moves to the end, then the slow pointer will be at position (length - n - 1) from the start. But wait, I want to remove the nth node from the end, so I actually want to stop at position (length - n) from the start, which means the slow pointer should be at the node just before the target.

Actually, let me think of a cleaner approach: I'll use a dummy node to handle edge cases uniformly. Then I'll advance one pointer n steps ahead, and then move both pointers together until the fast one reaches the end. At that point, the slow pointer will be pointing to the node just before the target node.

This approach is O(n) time and O(1) space, which is optimal for this problem since we must at least traverse the list once to find the target node.

The key insight is that instead of calculating the exact position, I can use the relative positioning between two pointers to identify the target node in a single traversal.

The invariant I must maintain is that the fast pointer is always exactly n steps ahead of the slow pointer, so when fast reaches the end, slow points to the node just before the one to remove.

public ListNode removeNthFromEnd(ListNode head, int n) {
    // Use dummy node to handle edge cases consistently
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    // Two pointers, fast starts n steps ahead
    ListNode slow = dummy;
    ListNode fast = dummy;
    
    // Advance fast pointer n steps
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    
    // Move both pointers until fast reaches the end
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    
    // Remove the nth node from end
    slow.next = slow.next.next;
    
    return dummy.next;
}

4. Data Structure Choice

For this problem, I'll use a singly linked list as the primary data structure, which is the natural representation for the input.

Primary Data Structures Used

1. ListNode class - The core data structure representing each node in the linked list

   • Contains val (integer value) and next (pointer to next node)
   • This is the standard definition for singly linked list nodes

2. Dummy Head Node - A sentinel node that simplifies edge case handling

   • Helps avoid special handling for removing the head node
   • Makes the two-pointer approach cleaner and more uniform

Why Each Data Structure Is Needed

The ListNode is essential because:

• It's the fundamental building block of the input data structure
• Each node needs to maintain its value and link to the next node
• This is the only data structure that can represent a linked list

The dummy head node is crucial for:

• Eliminating edge case handling when removing the first node
• Providing a consistent starting point for both pointers in the two-pointer approach
• Making the code more readable and less error-prone

Time and Space Impact

• Time: O(1) for node creation and access
• Space: O(1) additional space for the dummy node (constant extra space)
• The dummy node doesn't increase asymptotic complexity but improves code clarity

Helper Structure for Implementation

The dummy head node serves as a helper structure that simplifies the implementation by:

• Eliminating special case logic for head removal
• Providing a consistent reference point for pointer operations
• Reducing the chance of null pointer exceptions

This choice makes the solution clean, readable, and robust while maintaining optimal time and space complexity. The dummy node approach is a well-established pattern in linked list problems that significantly reduces implementation complexity without affecting performance characteristics.

5. Algorithm Walkthrough

Let me trace through the two-pointer approach with example input: 1->2->3->4->5, n = 2

Step 1: Initialize pointers

• fast = head (points to node 1)
• slow = head (points to node 1)

Step 2: Move fast pointer n steps ahead

• Move fast pointer 2 steps:
  • Step 1: fast → node 2
  • Step 2: fast → node 3
• Now fast points to node 3, slow points to node 1

Step 3: Move both pointers until fast reaches end

• Move both pointers:
  • Step 1: fast → node 4, slow → node 2
  • Step 2: fast → node 5, slow → node 3
• Now fast points to node 5 (null next), slow points to node 3

Step 4: Remove the nth node from end

• Since slow points to node 3, we need to remove node 4 (the next node)
• Set slow.next = slow.next.next (node 3's next becomes node 5)
• Result: 1->2->3->5

Edge case handling: If n = 5 (removing first node), fast would become null after 5 steps

• We'd detect this and return head.next (node 2) as new head
• This handles the case where we need to remove the first node

The algorithm correctly identifies that when fast reaches the end, slow points to the node just before the one we need to remove. This is because fast started n steps ahead, so when it reaches the end, slow has traversed exactly (length - n) nodes, which is the position of the node before our target.

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 find and remove the nth node from the end in a single pass. The dummy node simplifies edge case handling when removing the first node.

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 at most twice - once when advancing the fast pointer, and once when advancing the slow pointer. Since we're processing each node a constant number of times, the time complexity is linear in the size of the list.

Space Complexity: O(1)

The solution uses only a constant amount of extra space regardless of input size. We maintain just two pointers (fast and slow) and a few local variables, all requiring constant space. No additional data structures like arrays or hash maps are used.

Why these bounds are correct:

The linear time complexity is optimal for this problem because we must examine each node at least once to determine the nth node from the end. Since we're removing exactly one node, we must identify its position, which requires traversing the list. The constant space usage is optimal because we're only using a fixed number of pointers and variables, independent of the input size.

Optimality:

This solution achieves optimal time complexity O(n) and space complexity O(1). Any correct solution to this problem must process each node at least once to locate the target, making O(n) time unavoidable. The space complexity is already minimal since we're only tracking a few pointers.

The solution is optimal because:

1. We make exactly one pass through the list
2. We use only constant extra space
3. We handle all edge cases correctly with minimal overhead
4. No preprocessing or additional data structures are required

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty list: The solution must handle head == null gracefully, returning null
• Single node list: When n = 1, we should return null (remove the only node)
• Two node list: When n = 1, we remove the last node; when n = 2, we remove the first node

Duplicate Values and Repeated States

• The algorithm works regardless of duplicate values in the nodes
• The removal operation is based on position, not value, so duplicates don't affect correctness

Boundary Conditions

• n = 0: Should not occur per problem constraints (1 ≤ n ≤ sz)
• n = sz: Remove the first node (head), which requires special handling in the linked list structure
• n = sz - 1: Remove second-to-last node, requiring proper pointer adjustments

Common Implementation Mistakes

• Not handling the head removal case: When removing the first node, we must return head.next instead of modifying head
• Incorrect pointer updates: Failing to properly set prev.next = current.next when removing a middle node
• Off-by-one errors in the two-pointer technique: Miscounting positions when advancing pointers, particularly in the initial phase
• Failing to handle null references: Not checking if current or prev becomes null before accessing their next fields
• Not updating the head reference: When removing the first node, returning head.next instead of head

Implementation-Specific Pitfalls

• Using a dummy node incorrectly: While helpful for simplifying edge cases, improper dummy node handling can lead to incorrect references
• Missing the second pointer advancement: When implementing the two-pointer approach, forgetting to advance fast pointer n times before starting the second loop
• Not handling integer overflow: Though unlikely in this problem, if n were calculated from a large input, overflow considerations might be relevant

The solution must properly handle all these edge cases to ensure correctness across the entire spectrum of valid inputs.

9. Alternative Approaches

There are several alternative approaches to solving this problem, each with different trade-offs:

Two-Pass Approach:

• First pass: calculate the length of the list
• Second pass: find and remove the (length - n)th node from beginning
• 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
• Pop n nodes to find the target node
• Remove the nth node from stack top
• Time: O(n), Space: O(n)
• Uses extra space but is intuitive for those familiar with stack operations

Recursive Approach:

• Use recursion to traverse to the end, then count backward
• When count equals n, remove the next node
• Time: O(n), Space: O(n) due to recursion stack
• Elegant but uses call stack space and can hit stack overflow for very long lists

Hash Map Approach:

• Store references to all nodes in a HashMap with indices as keys
• Remove node at position (size - n)
• Time: O(n), Space: O(n)
• Simple but uses additional memory proportional to list size

The chosen two-pointer approach is preferred because it's optimal in both time and space complexity, requires only one pass, and doesn't use additional memory beyond a few pointers. The stack and recursive approaches are more intuitive but have higher space complexity, while the two-pass approach is less efficient due to multiple traversals.

10. Test Cases

// Test case 1: Basic functionality - remove middle element
// Input: [1,2,3,4,5], n = 2
// Expected: [1,2,3,5]
ListNode head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
ListNode result1 = removeNthFromEnd(head1, 2);

// Test case 2: Remove first element
// Input: [1,2,3], n = 3
// Expected: [2,3]
ListNode head2 = new ListNode(1);
head2.next = new ListNode(2);
head2.next.next = new ListNode(3);
ListNode result2 = removeNthFromEnd(head2, 3);

// Test case 3: Remove last element
// Input: [1,2,3], n = 1
// Expected: [1,2]
ListNode head3 = new ListNode(1);
head3.next = new ListNode(2);
head3.next.next = new ListNode(3);
ListNode result3 = removeNthFromEnd(head3, 1);

// Test case 4: Single element list
// Input: [1], n = 1
// Expected: []
ListNode head4 = new ListNode(1);
ListNode result4 = removeNthFromEnd(head4, 1);

// Test case 5: Empty list
// Input: [], n = 1
// Expected: []
ListNode result5 = removeNthFromEnd(null, 1);

// Test case 6: Duplicate values
// Input: [1,2,2,3], n = 2
// Expected: [1,2,3]
ListNode head6 = new ListNode(1);
head6.next = new ListNode(2);
head6.next.next = new ListNode(2);
head6.next.next.next = new ListNode(3);
ListNode result6 = removeNthFromEnd(head6, 2);

The test cases cover:

• Basic functionality with middle element removal
• Edge case of removing the first element
• Edge case of removing the last element
• Boundary case of single-element list
• Boundary case of empty list
• Duplicate values in the list

Each test validates different aspects of the solution's correctness and handles various edge conditions that could break a naive implementation.

11. Final Summary

The core insight is to use the two-pointer technique with a fixed-distance gap to find and remove the nth node from the end in a single pass. This approach efficiently handles the linked list traversal by maintaining a consistent relative position between two pointers, making it both time and space optimal for this problem. The solution elegantly avoids needing to first calculate the list length, demonstrating how thoughtful pointer manipulation can simplify linked list operations.