Reverse a single linked list in O(n) time and in-place.

reverse_list.cpp

void reverseList(list **l) {
  if ((*l)->next == NULL) return;

  // Hold the current list pointer for use in the actual swap, then assign the
  // list pointer to the next element to place us at the correct head.
  list *cur = *l;
  *l = (*l)->next;

  // Recurse with the new list pointer.  This allows us to traverse to the
  // farthest element while maintaining O(n) time.
  reverseList(&(*l));

  cur->next->next = cur;
  cur->next = NULL; // Remove the old next link.
}