</>EmbeddedInterview

Find the nth node from the end of a linked list (and remove it).

Easy"Coding: Linked Lists, Stacks & Queues"
/* returns the nth node from the end (n = 1 is the last), or NULL */
node_t *nth_from_end(node_t *head, unsigned n)
{
    node_t *lead = head, *trail = head;
    for (unsigned i = 0; i < n; i++) {
        if (!lead) return NULL;                   /* list shorter than n */
        lead = lead->next;
    }
    while (lead) { lead = lead->next; trail = trail->next; }
    return trail;
}

void remove_nth_from_end(node_t **head, unsigned n)
{
    node_t **pp = head, *lead = *head;
    for (unsigned i = 0; i < n; i++) { if (!lead) return; lead = lead->next; }
    while (lead) { lead = lead->next; pp = &(*pp)->next; }
    node_t *dead = *pp;
    *pp = dead->next;
    free(dead);
}

Points: two pointers n apart: when the leader falls off the end, the trailer is at the answer. One pass, O(1) space. Handle n larger than the list and n == length (removing the head).