Reversing singly Link List

Consider you have a single link list as below:

4 -> 8 -> 1 -> NULL

and you want to reverse this list as

1 -> 8 -> 4 -> NULL

In order to reverse the list we have to make the next pointer of your node to point to earlier element in the list as below.

Original List:

4 -> 8 -> 1 -> NULL

Reversed List:

NULL <- 4 <- 8 <- 1

Now how can we make this happen. Remove one element at a time from the original list and put it to new list at the beginning as shown below.

Original List:

4 -> 8 -> 1 -> NULL

New two lists:

4 ->NULL     &  8 -> 1 -> NULL

Here we are not allocating any memory using new for new list, we have just dis-joined it from original list, follow same steps till end and you are done.

Original List:

4 -> 8 -> 1 -> NULL

New two lists:

8 -> 4 ->NULL     &  1 -> NULL

Original List:

4 -> 8 -> 1 -> NULL

New lists:

1 -> 8 -> 4 ->NULL

Following is the code for the above mentioned :

Node * ReverseList(Node * pHead) {     if (pHead)     {         Node * pLastNode = NULL;         while (pHead)         {             Node * pTemp = pHead->pNext;             pHead->pNext = pLastNode;             pLastNode = pHead;             pHead = pTemp;         }         return pLastNode;     }     return NULL; }

Here Node is struct of type: 

struct Node

{ 

    int data;  //This can be any data type

    Node * Next; 

};