Singly Linked List Reversal

The problem: Given a list with one direction link, return a list with all links reversed, i.e. with all elements linked in reversal order.

A typical implementation, where reversal starts from the beginning of the list, would look like this:

		
	struct node {
	   int val;
	   node *_pnext;
	};
	node *ReverseList(node *p)
	{
	   node *pLast=0, *pNext=0;
	   while(p!=0)
	   {
	      pNext = p->_pnext;
	      p->_pnext = pLast;
	      pLast = p;
	      p = pNext;
	   }
	   return pLast;
	}
	

Here is a different implmentation, where the reversal starts from the end of the list, that can be implemented with recursive call:

		
	node *RecurReverseList(node *p)
	{
	   if (p==0) return p;
	   if(p->_pnext)
	   {
	        node *pR = RecurReverseList(p->_pnext);
	        (p->_pnext)->_pnext = p;
	        p->_pnext = 0;
	        return pR;
	   }
	   else
	        return p;
	}