Problem Statement

Given the head of a singly linked list and an integer n, return the head of the list after removing the nth node from the end of the list. You may assume that n is always valid and that the list contains at least one node.

LeetCode: 19. Remove Nth Node From End of List

Difficulty: Medium

How the Algorithm Works

💡 One Sentence Rule (Key Insight)

Maintain two pointers with a fixed n-node gap; when the leading pointer reaches the end, the trailing pointer is positioned just before the node to remove.

This rule captures the ESSENCE of the algorithm. Every step we take follows from this rule.

Algorithm Overview

The key insight is that the nth node from the end is the (length - n + 1)th node from the start. However, we don't need to calculate the length separately. By maintaining two pointers separated by exactly n nodes, we can identify the target position in a single pass.

We use a dummy node to handle edge cases (like removing the head) gracefully. The dummy points to the actual head, allowing us to modify the head if needed without special case logic.

Step-by-Step Process

When we need to remove the nth node from the end:

  1. Create dummy node pointing to head ← Handles edge case where head is removed
  2. Initialize two pointers: left at dummy, right at head ← Start with 1-node gap
  3. Move right pointer n steps forward ← Establish n-node gap between pointers
  4. Move both pointers together until right reaches end ← Maintain gap; when right is at end, left is before target
  5. Skip the target node: left.next = left.next.next ← Remove the nth node
  6. Return dummy.next as the new head ← May be different if head was removed

Why It Works

The algorithm works because of a simple mathematical relationship:

  • If the list has L nodes
  • The nth node from the end is at position L - n from the start (0-indexed)
  • When right pointer is at position L - 1 (the last node but actually None after the loop)
  • The left pointer is at position L - 1 - n = L - n - 1
  • This is exactly one position before the node we want to remove

Input

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

Output

[1,2,3,5]

Explanation: The 2nd node from the end is node with value 4. After removing it, the list becomes [1,2,3,5].

Solution

def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
    """Remove the nth node from the end of a linked list in one pass."""
    # Create dummy node to handle edge case where head is removed
    dummy = ListNode(0, head)
    left = dummy
    right = head
    
    # Move right pointer n steps ahead to create gap
    while n > 0 and right:
        right = right.next
        n -= 1
    
    # Move both pointers until right reaches the end
    # When right is None, left is just before the target node
    while right:
        left = left.next
        right = right.next
    
    # Skip the nth node from the end
    left.next = left.next.next
    
    # Return new head (might be different if original head was removed)
    return dummy.next

Complexity Analysis

Time Complexity: O(L) where L is the length of the linked list

  • We traverse the list once with the right pointer (n steps + remaining steps)
  • We traverse with both pointers together (L - n steps)
  • Total operations: n + (L - n) = L

Space Complexity: O(1)

  • We only use two pointers and a dummy node
  • No additional data structures that grow with input size

Applying the One Sentence Rule

Use two pointers when you can make progress by moving pointers based on comparisons or relationships, eliminating the need to check all pairs.

For this problem:

  • What relationship do we maintain? Fixed gap of exactly n nodes between pointers
  • How do we make progress? Move pointers together, maintaining the gap
  • What does the relationship tell us? When right reaches end, left is before the target
  • Do we check all pairs? ✗ No - single pass with coordinated movement

Applying the rule:

The fixed-gap two pointer technique works perfectly here because the relationship between "nth from end" and "position to stop" is constant. Once we establish the gap, we don't need to recalculate positions or make any decisions - just move together until reaching the end.

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

  1. Setup: dummy→1→2→3→4→5, left=dummy, right=head(1)
  2. Create gap (n=2): Move right 2 steps → right=3, gap established
  3. Move together:
    • right=3, left=dummy→1 → move → right=4, left=1→2
    • right=4, left=1→2 → move → right=5, left=2→3
    • right=5, left=2→3 → move → right=None, left=3→4 ✓ Stop
  4. Remove: left.next = left.next.next → skip node 4
  5. Result: dummy→1→2→3→5

The beauty of this approach is that we never need to know the total length. The fixed gap automatically positions us correctly when the leading pointer runs out.

Key Insights

  1. Dummy Node Pattern: Using a dummy node eliminates special case handling for removing the head. The dummy always remains, so we never lose the reference to the list.

  2. Gap Mathematics: The gap of n nodes means when right is at the end (None), left is at position (length - n - 1), which is exactly one position before the target node at (length - n).

  3. Single Pass: Unlike naive approaches that require two passes (one to find length, one to remove), this uses coordinated pointer movement for a single-pass solution.

  4. Edge Cases Handled: The dummy node approach naturally handles:

    • Removing the head (when n equals list length)
    • Single-node lists
    • Any valid n value

  5. Fixed Gap vs Other Two Pointer Variants: This is a fixed-gap two pointer problem, different from converging pointers (Two Sum II) or fast/slow pointers (cycle detection). The gap remains constant throughout execution.