Reverse a Linked List

This question is one of the most repeated ones across Google, Microsoft, Amazon and a few more. The thing which makes it a good question is that after you scratch your head and give them an algorithm they either ask you to optimize it for the boundary cases (which is fine for most of the candidates) or they ask you to do it the other way round.

I am going to give you both, recursive as well as an iterative solution. For both the techniques :

Initially call the method as : head = reverseList(head,NULL)


Iterative :

Node *Reverse (Node *p)
{
   Node *pr = NULL;
   while (p != NULL)
   {
      Node *tmp = p->next;
      p->next = pr;
      pr = p;
      p = tmp;
   }
   return pr;
}
-----------------------------------------------------------------------
Recursive:

Node *reverseList(Node *current, Node *parent)
{
        Node *revHead;
   if(current == null)
      revHead = parent;
   else
   {
      revHead = reverseList(current->next,current);
      current->next = parent;      
   }
   return revHead;
}