Remove Nth Node

Removing the Nth node from the end of a linked list is a perfect warm-up for real-world tasks like trimming logs, pruning history buffers, or deleting stale data entries. It tests your ability to manipulate pointers in-place without extra memory.

Problem Statement

Given the head of a singly linked list and an integer n, remove the Nth node from the end of the list and return its head. You must solve this in one pass with O(1) extra space if possible.

// Definition provided in interview
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// Signature:
public ListNode removeNthFromEnd(ListNode head, int n);

1. Clarify Requirements Before Jumping Into Code

I need to confirm a few details:

Is n always valid (1 ≤ n ≤ list length)? Yes.
Should I handle an empty list? If head is null, just return null.
Removing the head (n == length) should return the second node as new head.
Can I modify pointers in-place? Yes.
Aim for one-pass and constant extra memory.

2. Identify the Category of the Question

This is a linked list manipulation problem. Common patterns in this category include:

Dummy head node to simplify edge cases
Two-pointer (fast/slow) to find positions relative to list end
Length-count then remove (two-pass)
Recursion to unwind from end
Stack to track nodes

Recognizing “Nth from end” hints at a two-pointer gap approach.

3. Consider a Brute-Force Approach to Understand the Problem

Brute-force:

Traverse the list to compute its length L.
Compute the index from start: idx = L - n.
Traverse again to the node just before idx, adjust its next to skip the target.
Time Complexity: O(n) + O(n) = O(n)
Space Complexity: O(1)
Works, but uses two passes instead of one.

4. Brainstorm More Solutions

I want a true one-pass method. Ideas include:

Two-pointer gap: Move a "fast" pointer n+1 steps ahead of a slow pointer (starting from a dummy). Then advance both until the fast pointer hits the end of the list. At that point, slow.next is the node to remove. This needs only one traversal and constant space.
Recursion:Recurse to the end, unwind with a counter. When the counter reaches n, skip the current node. This is elegant but uses O(n) call stack.
Stack:Push all nodes onto a stack, then pop n nodes; the next top is the node before the removal target. Also O(n) space.

Since I need to locate a node relative to the end without knowing the length, the two-pointer gap method seems ideal. I can keep two pointers separated by n nodes. When the fast pointer reaches the end, the slow pointer ends up exactly the required distance from the end.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Two-pass length	O(n)	O(1)	Simple, no recursion	Requires two traversals
Two-pointer single	O(n)	O(1)	Single pass, constant space	Slightly trickier pointer logic
Recursion	O(n)	O(n)	Elegant unwind logic	Uses call stack memory
Stack	O(n)	O(n)	Intuitive with explicit stack	Extra O(n) memory

Two-pointer single-pass is optimal in both time and space.

6. Write Pseudocode to Structure Your Thoughts

function removeNthFromEnd(head, n):
  dummy = new ListNode(0)
  dummy.next = head
  slow = dummy
  fast = dummy

  // Move fast ahead by n+1 steps
  for i in 1 to n+1:
    fast = fast.next

  // Move both until fast is at end
  while fast != null:
    fast = fast.next
    slow = slow.next

  // Remove nth node
  slow.next = slow.next.next

  return dummy.next

7. Consider Edge Cases

Empty list (head = null) → return null
Single node, n=1 → removes head → return null
Remove head (n == length) → dummy.next updates to second node
Remove tail (n == 1) → last node skipped
Normal case (n in middle) → correct node skipped

8. Write Full Code Syntax

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode fast = dummy;
        ListNode slow = dummy;
        
        // Advance fast by n+1
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        
        // Move both pointers
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        // Skip the target node
        slow.next = slow.next.next;
        return dummy.next;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();
    
    // Helper functions buildList and toArray omitted for brevity
    
    // Test 1: remove middle
    assert Arrays.equals(
        sol.removeNthFromEnd(buildList(1,2,3,4,5), 2).toArray(),
        new int[]{1,2,3,5}
    );
    
    // Test 2: remove head
    assert Arrays.equals(
        sol.removeNthFromEnd(buildList(1,2), 2).toArray(),
        new int[]{2}
    );
    
    // Test 3: remove tail
    assert Arrays.equals(
        sol.removeNthFromEnd(buildList(1,2,3), 1).toArray(),
        new int[]{1,2}
    );
    
    // Test 4: single node
    assert sol.removeNthFromEnd(buildList(1), 1) == null;
    
    // Test 5: two nodes remove second
    assert Arrays.equals(
        sol.removeNthFromEnd(buildList(1,2), 1).toArray(),
        new int[]{1}
    );
    
    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

Using a dummy head simplifies edge-case removal at the head.
Two-pointer gap pattern finds “Nth from end” in one pass without knowing length.
Always advance the fast pointer n+1 from dummy so slow lands just before the target.
Writing clear pseudocode for pointer movement prevents off-by-one errors.
Test edge cases: empty list, single node, removal of head/tail, and normal scenarios.
Discussing multiple approaches and trade-offs demonstrates depth and flexibility.

Good Luck and Happy Coding!