Reverse a linked List
Tags: c, array, linkedlist
Published: 2022-06-03 10:05:01

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](https://www.coderlogs.com/post/627a4309752339739aa908d9/implementation-of-Linked-List-in-C--).

Lets assume that the linked list is already created as shown in fig below,

![image](https://i.ibb.co/CJ9x736/IMG-20220512-150607.jpg)

**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` and `nextnode` 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 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.
![image](https://i.ibb.co/gyM98Xb/IMG-20220519-192223.jpg)

*  **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.
 ![image](https://i.ibb.co/3rSjsjf/IMG-20220519-194341.jpg)

* **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.
![image](https://i.ibb.co/LSMD5nf/IMG-20220519-193255.jpg)

* **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. 
![image](https://i.ibb.co/9vdq9LR/IMG-20220519-195201.jpg)

* 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`. 
**head = prevnode;** ![image](https://i.ibb.co/Qk08yNq/IMG-20220519-195555.jpg)

* 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.