Here we will discuss two most popular methods for reversing a link list - the
iterative method and the
recursive method.
Iterative method
The first is the iterative method. Here we require 3 extra pointers other than the start pointer - the ptr pointer, which starts from start pointer and traverses the linked list; the previous pointer, which initially points to NULL, and then to ptr; the temp pointer, which points to the next pointer of ptr.
 |
| Reversing a linked list - iterative method |
Here's the code for iterative solution. The time complexity is O(n).
void reverse()
{ node *ptr = start;
node * temp;
node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
start = previous;
}
Recursive method
The next method is the recursive method. It uses a recursive function and two extra pointers - p and rest. 'p' points to the first node and 'rest' to the next node, i.e., the rest of the linked list. We recursively move to the end of the linked list such that p is now the second last node and rest points to the last node. Then we link the next pointer of rest to p, and the next pointer of p to NULL, till we reach the first element. We also change the start pointer to point to rest.
void revp(node **start)
{ node *p;
p=*start;
if(p==NULL) return;
node * rest = p->next;
if(rest == NULL) return;
revp(&rest);
p->next->next = p;
p->next=NULL;
*start = rest;
}
If you do not wish to actually reverse the list, but only print what its reverse might look like, you may follow this method:
void rev(node *start)
{ if(start==NULL)
return;
rev(start->next);
printf("%d",start->data);
}
Finally, the program may look something like this:
#include <stdio.h>
#include <stdlib.h>
typedef struct node node;
struct node{ int data; node *next;
} *start=NULL;
void insert(int val)
{ node *temp = (node *)malloc(sizeof(node));
temp->data=val;
if(start==NULL)
{ start = temp;
temp->next = NULL;
}
else
{ node *ptr=start;
while(ptr->next)
{ptr=ptr->next;}
ptr->next = temp;
temp->next = NULL;
}
}
void display()
{ node *temp = start;
printf("\n");
while(temp)
{printf(" %d ",temp->data);
temp = temp->next;
}
printf("\n");
}
//ITERATIVE SOLUTION
void reverse()
{ node *ptr = start;
node * temp;
node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
start = previous;
}
//RECURSIVE SOLUTIONS
//ONLY PRINTD THE REVERSE OF LIST (NO LINKS ARE REVERSED)
void rev(node *start)
{ if(start==NULL)
return;
rev(start->next);
printf("%d",start->data);
}
//REVERSES THE ACTUAL LIST (ALL LINKS ARE REVERSED)
void revp(node **start)
{ node *p;
p=*start;
if(p==NULL) return;
rest = p->next;
if(rest == NULL) return;
revp(&rest);
p->next->next = p;
p->next=NULL;
*start = rest;
}
int main()
{
insert(1);insert(2);insert(3);insert(4);insert(5);insert(6);insert(7);
display();
//reverse();
//rev(start);
revp(&start);
printf("\nReversed:\n");
display();
return 0;
}
