Thursday, August 16, 2012

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

No comments:

Post a Comment