A given linked list can be reversed in two ways :
- Using loop
- Using recursion (iterative) method.
Here, you will learn the iterative method
for reversing a given linked list.
To understand the process of reversing a linked list, you must have the knowledge of creating and displaying the linked list. To know the implementation of linked list click here.
Lets assume that the linked list is already created as shown in fig below,
Fig.1 Linked list
Here in iterative method
, the data elements of the linked list are not reversed directly but the links
that connects each node starting from the head
node to the last node are reversed.
The links
are reversed by replacing the address of next node with the address of previous node. After reversing all the links
of the linked list, the detached head
node from the first node is connected to the last node in the list.
Steps to reverse a given linked list :
Take three pointers of type
struct node
to point the previous node, current node and the next node in the list.
struct node *prevnode, *currentnode, *nextnode;Make pointers
currentnode
andnextnode
to point first node in the list.
currentnode = nextnode = *head;Initialize the pointer
prevnode
.
prevnode = 0;-
Using while loop, 1st iteration : Breaks the forward link between first and second node.
- Make
nextnode
to point second node in the list by accessing the address part of the first node as it contains the address of next node using structure membernext
. nextnode = nextnode->next; - Replace the address part of the first node with the
prevnode
. By doing this, the link between first node and the second node will be broken. Note : In reversing, the first node has to be made the last node in the list hence the address part of the first node is replaced byNULL
. currentnode->next = prevnode; - The first node is the previous node for the second node hence, this first node address is saved into
prevnode
for further process. As shown in the above fig.1, the address of first node is assumed as100
so this100
is copied intoprevnode
. prevnode = currentnode; - Pointer
currentnode
is made to point to the second node(to which pointernextnode
is pointing) for further process. currentnode = nextnode; Note : Positions of pointer after 1st iteration :nextnode
andcurrentnode
points second node.prevnode
points first node.
- Make
-
2nd iteration : Breaks the forward link between second and third node and creates a reverse link between first and second node.
- Make
nextnode
to point third node in the list. - Replace the address part of second node with
prevnode
which contains the address of first node. By doing this, the forward link between second and third node will be broken and the reverse link between second and first node will be created. - Store the address of second node into
prevnode
for further process. As shown in the above fig.1, the address of second node is assumed as200
so this200
is copied into prevnode. - Point
currentnode
to the third node. Note : Positions of pointer after 2nd iteration :nextnode
andcurrentnode
points third node.prevnode
points second node.
- Make
3rd iteration : Breaks the forward link between third and fourth node and creates a reverse link between second and third node.
Note : Positions of pointer after 3rd iteration :nextnode
andcurrentnode
points fourth node.prevnode
points third node.
4th iteration : Creates a reverse link between third and fourth node and all the links get reversed.
Note : Positions of pointer after 4th iteration :currentnode
andnextnode
containsNULL
.prevnode
points fourth node.
After all the iterations, the
prevnode
points the fourth node whose address is assumed as400
as shown in the above fig.1. To attach thehead
node to this fourth node, copyprevnode
tohead
.
head = prevnode;Display the reversed linked list.
C code that demonstrates the reverse of a linked list :
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
void reverseLL(struct node * *head)
{
struct node * prevnode, * currentnode, * nextnode;
prevnode = 0;
currentnode = nextnode = * head;
while(nextnode != 0)
{
nextnode = nextnode->next;
currentnode->next = prevnode;
prevnode = currentnode;
currentnode = nextnode;
}
*head = prevnode;
}
void displayLL(struct node *head)
{
struct node *temp;
temp = head;
while(temp!=0)
{
printf("%d ",temp->data);
temp = temp->next;
}
}
int main()
{
struct node *head = 0, *newnode, *temp;
int count=0, n, choice, newdata;
printf("Enter the number of nodes in the list : ");
scanf("%d", &n);
for(int i = 1; i<=n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data%d : ", i);
scanf("%d", &newnode->data);
newnode->next = 0;
if(head == 0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}
printf("--------------------------------\n");
printf("Linked list : ");
displayLL(head);
reverseLL(&head);
printf("\nReverse linked list : ");
displayLL(head);
}
`
I own a website www.coderlogs.com where in I write similar blogs so do visit the website for more such blog posts.
Top comments (0)