Hi,
Yesterday I was thinking of different ways to reverse a linked list.Here are the best ones I worked on:
Assume the following structure definition:
struct llist
{
int data;
llist *next;
};
3 Pointer method(with decomposition):
llist * reverselist_3p(llist * start)
{
llist * current = start; //Pointer 1: To store the current node
llist * nexttocurrent = NULL; //Pointer 2: To store the node next to current
llist * temp = NULL; //Pointer 3: To temporarily store node just detached from the main list, so that we can assign it to the ‘current’ in the next iteration
while(current!=NULL)
{
nexttocurrent = current->next;
current->next = temp;
temp = current;
current = nexttocurrent;
}
return temp;
}
3 Pointer method(without decomposition):
llist * reverselist_2p(llist * start)
{
llist * back = NULL; //Pointer 1: To store the back node
llist * middle = start; //Pointer 2: Middle node
llist * front = middle->next; //Pointer 3: Front node
while(front!=NULL)
{
middle->next = back;
back = middle;
middle = front;
front = front->next;
}
middle->next=back;
return middle;
}
2-3 Pointer method (A beautiful Recursion) : # My favorite
![]()
llist * reverselist_re(llist * start)
{
if(start==NULL)
return NULL;
llist * first = start;
llist * rest = first->next;
if(rest==NULL)
return first;
start=reverselist_re(rest); //you may argue that start is the 3rd pointer
first->next->next = first;
first->next = NULL;
return start;
}
If you like this post, please post you valuable comments.