# Remove Nth Node From End of List

- **Canonical ID**: `remove-nth-node-from-end-of-list`
- **Canonical URL**: https://dsacheatsheet.com/problems/remove-nth-node-from-end-of-list
- **Difficulty**: medium
- **Patterns**: Linked Lists
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

## 1. Core Invariant / The Trick

Attach a `dummy` before `head`. Advance `right` `n + 1` steps ahead of `left = dummy`, or advance `right` `n` steps then step both until `right.next == null` so `left` lands cleanly on the predecessor.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Single one-pass scan preserving exact `n`-node separation between `left` and `right`.

## 3. Minimal Idiomatic Code

### Python
```python
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    left = right = dummy
    for _ in range(n):
        right = right.next
    while right.next:
        left = left.next
        right = right.next
    left.next = left.next.next
    return dummy.next
```

### TypeScript
```typescript
export function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let left = dummy;
  let right = dummy;
  for (let i = 0; i < n; i++) right = right.next!;
  while (right.next !== null) {
    left = left.next!;
    right = right.next;
  }
  left.next = left.next!.next;
  return dummy.next;
}
```

### C++
```cpp
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head), *left = &dummy, *right = &dummy;
    for (int i = 0; i < n; ++i) right = right->next;
    while (right->next) { left = left->next; right = right->next; }
    left->next = left->next->next;
    return dummy.next;
}
```

### Java
```java
ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head), left = dummy, right = dummy;
    for (int i = 0; i < n; i++) right = right.next;
    while (right.next != null) { left = left.next; right = right.next; }
    left.next = left.next.next;
    return dummy.next;
}
```

### Go
```go
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    left, right := dummy, dummy
    for i := 0; i < n; i++ { right = right.Next }
    for right.Next != nil { left, right = left.Next, right.Next }
    left.Next = left.Next.Next
    return dummy.Next
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Deleting the head node (`n == length`) crashes without a dummy node before `head`.
- Off-by-one step count stops `left` on the target node instead of its predecessor.

### Follow-ups
- Delete the Middle Node of a Linked List uses `dummy` + fast/slow pointers with the same predecessor pattern.