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;
};
