Skip to main content

19 - Remove Nth Node From End of List

Difficulty: Medium | Pattern: Two Pointers (Fast/Slow) | Company tags: Amazon, Microsoft, Facebook, Apple

Problem Statement​

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

Example 1:

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

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Approach: Two Pointers (One Pass) — O(n), O(1)​

Key insight: Use a dummy node and two pointers fast and slow. Advance fast by n+1 steps first. Then move both until fast is None. slow will be just before the node to delete.

def removeNthFromEnd(head, n: int):
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy
    
    # Advance fast by n+1 steps
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both until fast is None
    while fast:
        fast = fast.next
        slow = slow.next
    
    # slow is just before the node to delete
    slow.next = slow.next.next
    
    return dummy.next

Dry Run​

head = [1,2,3,4,5], n=2 (remove 4, the 2nd from end)

  • dummy→1→2→3→4→5→None
  • Advance fast n+1=3 steps from dummy: fast points to 3
  • Move both: fast=4, slow=1; fast=5, slow=2; fast=None, slow=3
  • slow.next = slow.next.next → 3→5 (skip 4)

Result: [1,2,3,5] ✓

Why n+1 Steps?​

Moving n steps positions fast such that after moving both to exhaustion, slow lands on the target node. Moving n+1 makes slow land before it — enabling deletion.

Edge Cases​

  • n = len(list) → remove the head (dummy node handles this gracefully)
  • Single node → returns empty list
  • n = 1 → remove the last node

Complexity​

  • Time: O(L) where L = list length
  • Space: O(1)