Nth from End

Finding the Nth Node from the End

To find the nth node from the end in one pass, use two pointers:

1. Advance fast by n steps
2. Move both fast and slow together until fast reaches NULL
3. slow is now at the nth node from the end

struct Node *nth_from_end(struct Node *head, int n) {
    struct Node *fast = head;
    struct Node *slow = head;
    while (n > 0 && fast != NULL) {
        fast = fast->next;
        n--;
    }
    if (fast == NULL && n > 0) return NULL; // out of bounds
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

Why It Works

List: [1] -> [2] -> [3] -> [4] -> [5] -> NULL    n=2

Step 1 — advance fast by 2:
  fast               → [3]
  slow               → [1]

Step 2 — move both until fast is NULL:
  fast [3]->[4]->[5]->NULL  (2 steps)
  slow [1]->[2]->[3]        (2 steps)

slow points to [3] — the 2nd node from the end ✓

Your Task

Implement struct Node *nth_from_end(struct Node *head, int n) that returns the nth node from the end (1-indexed), or NULL if out of bounds.