## DEV Community

Dhanashree Rugi

Posted on

A given linked list can be reversed in two ways :

1. Using loop
2. 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,

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` and `nextnode` to point first node in the list.

• 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 member `next`. 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 by `NULL`. 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 as `100` so this `100` is copied into `prevnode`. prevnode = currentnode;
• Pointer `currentnode` is made to point to the second node(to which pointer `nextnode` is pointing) for further process. currentnode = nextnode; Note : Positions of pointer after 1st iteration : `nextnode` and `currentnode` points second node. `prevnode` points first node.
• 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 as `200` so this `200` is copied into prevnode.
• Point `currentnode` to the third node. Note : Positions of pointer after 2nd iteration :`nextnode` and `currentnode` points third node. `prevnode` points second node.
• 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` and `currentnode` 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` and `nextnode` contains `NULL`. `prevnode` points fourth node.

• After all the iterations, the `prevnode` points the fourth node whose address is assumed as `400` as shown in the above fig.1. To attach the `head` node to this fourth node, copy `prevnode` to `head`.

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

{
struct node * prevnode, * currentnode, * nextnode;
prevnode = 0;
currentnode = nextnode = * head;
while(nextnode != 0)
{
nextnode = nextnode->next;
currentnode->next = prevnode;
prevnode = currentnode;
currentnode = nextnode;
}
}

{
struct node *temp;
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;
{
}
else
{
temp->next = newnode;
temp = newnode;
}
}
printf("--------------------------------\n");