How to reverse a (singly) linked list is allegedly a popular job interview question. If that is true, it says something about the skill of the "ordinary programmer". It is also common as a brain teaser, and an exercise in computer science classes.
One reason it is popular is that there exists an obvious, elegant, and wrong answer, given in the following pseudocode:
fun reverse(list) =
if (list == null)
null;
else
append(reverse(tail(list)), head(list));
(Exercise: list three reasons the above code is inefficient). The nice way to do it is to maintain two lists, the input list in and an output list out that is initialized to NULL. Then for each iteration, you move the first item of in to the beginning of out. When you have moved all the items, you return out. (Think of reversing a deck of cards by repeatedly moving the top card from one stack to the other).
If you modify the nodes that made up the input list, this works in linear time, constant space, and allocates no new storage. C code:
node *reverse (node *in) {
node *out = NULL;
while (in) {
node *tmp = in->next;
in->next = out;
out = in;
in = tmp;
}
return out;
}