So we have a linked list of arbitrary size. A node in this list has this form: 
struct node {int data; node * next;};
in C++ speak.

Given a well formed list (without loops & ends with a null pointer), what is the fastest way to reverse the list?
What is the method that uses the least memory?
5 days later
Oh, no one answered this! :P
This is one of the questions that turned lots of people who call themselves coders in some job interviews. lol.
Here is a quick solution:
Node* ReverseList( Node ** List )             
{
              Node *temp1 = *List;
              Node * temp2 = NULL;
              Node * temp3 = NULL;
              while ( temp1 )
              {
                            *List = temp1;          
                            temp2= temp1->pNext;
                            temp1->pNext = temp3;
                            temp3 = temp1;
                            temp1 = temp2;
              }
              return *List;
}
Try to optimize it if you could :P
So loop will exit once temp1 == null ?
rahmu wroteSo loop will exit once temp1 == null ?
Sure.
All you need to do is make the pointers point the other way.
For example A points to B points to C...
you just need to reverse the pointers in all of them so that C points to B points to A...
So iterate the nodes and make every one point to it's ancestor (= preceding node or parent node).

I'm not good at C/C++ so I can only write pseudo code:

pointer to parent node = null

For each node {
temp = pointer to next node
pointer to next node = pointer to parent node
pointer to parent node = pointer to this node
}