Find the nth node from the end of a linked list (and remove it).
/* 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).