Reverse a linked List

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,

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.

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