Linked List reversal – Implementation and Explanation

Reversing a linked list is one of the most commonly asked data structure interview questions.
Shown the linked list 10, 20, 30.

After reversed operation, it should be 30, 20, 10.

Read more – Introduction to Linked List – Explanation and Implementation

Implementation

There are two approaches,

1. Iterative
2. Recursive

1. Iterative approach to reverse a Linked list:

It refers to the use of loop. Our target is to swap the position of first node with last node,  second node as second last node and so on. The logic we use here is that with each iteration a node is from the existing list is cut down and added as a node to the front of another linked list which is finally the reverse of the actual linked list.

list = list->next

The node that is cut down will be added to the new linked list. 1st time loop executed temp2 contains NULL(line no. 17) and temp1 contains the address of 1st node(line no. 20). With line no. 22 a reversed linked list of 1 element is created.
With the execution of 2nd time loop second node address of linked list is added to temp1. On reaching line no. 22, reversed linked list with 2 node is created.
When all the nodes in the linked list are traversed temp1 will have the address of head of reversed linked list.

Implementation in C to reverse a Linked list

#include<stdio.h>
#include<stdlib.h>
 
//DECLARATION
struct node 
{
    int data;
    struct node *next;
};
 
 //This function causes reverse of the linked list
struct node * reverseLinkedlist(struct node *head)
{
    struct node *list = head;   
    struct node *temp1 = NULL, *temp2;
 
    while (list != NULL)
    {
        temp2 = temp1;   //temp2 is storing the previous node
        temp1 = list;
        list = list->next;
        temp1->next = temp2; //temp1 is forming the reverse of linked list
    }
 
    return temp1;  //return the new head i.e. address of last node
     
}
 
// This function prints contents of linked list from given node
void printLinkedList(struct node *list)
{
    while (list)
    {
        printf(" %d ", list->data);
        list = list->next; // accessing and assigning the next element of list
    }
}
 
 
// Main method to initialize the program
int main()
{
    //INITIALIZATION
    //Declare and allocate 3 nodes in the heap 
    struct node* head;
    struct node* first = (struct node*)malloc(sizeof(struct node)); 
    struct node* second = (struct node*)malloc(sizeof(struct node));
    struct node* third = (struct node*)malloc(sizeof(struct node));
     
    //ASSIGNINMENT
    first->data = 10; //assign data in first node
    first->next = second; // Link first node with second 
     
    second->data = 20; //assign data to second node
    second->next = third; 
     
    third->data = 30; //assign data to third node
    third->next = NULL;
 
    head = first;    //head pointing to the linked list
 
    printf("Before Reversed Operation: ");
    printLinkedList(head);
 
    head = reverseLinkedlist(head);
    printf("\nAfter Reversed Operation: ");
   printLinkedList(head);
     
    return 0;
}

Output:-

Before Reversed Operation: 10 20 30
After Reversed Operation: 30 20 10

2. Recursive approach to reverse a Linked list :

Under this first we try to get the address of last node and in its way back we set the next  of every node as it’s previous node. After recursive calling of reversedLinkedlist, when base condition met i.e. line no. 17 then it returns the address of last node. As a result revHead will have last node address. This will be the head of the reversed linked list, which must be retained throughout the function being executed and finally returned to main program.
Line no. 19 and 20 causes to add the current node as the last node to the reversed linked list. It’s like see below

Implementation in C reverse a Linked list

#include<stdio.h>
#include<stdlib.h>
 
//DECLARATION
struct node 
{
   int data;
   struct node *next;
};
 
 //This function causes reverse of the linked list
struct node * reverseLinkedlist(struct node *list)
{
     
   struct node *revHead;
     
   if(list->next == NULL)  //base condition
    return list;
 
   revHead = reverseLinkedlist(list->next);
   list->next->next = list;
   list->next = NULL;
   return revHead; 
     
}
 
// This function prints contents of linked list from given node
void printLinkedList(struct node *list)
{
    while (list)
    {
        printf(" %d ", list->data);
        list = list->next; // accessing and assigning the next element of list
    }
}
 
 
// Main method to initialize the program
int main()
{
    //INITIALIZATION
    //Declare and allocate 3 nodes in the heap 
    struct node* head;
    struct node* first = (struct node*)malloc(sizeof(struct node)); 
    struct node* second = (struct node*)malloc(sizeof(struct node));
    struct node* third = (struct node*)malloc(sizeof(struct node));
     
    //ASSIGNINMENT
    first->data = 10; //assign data in first node
    first->next = second; // Link first node with second 
     
    second->data = 20; //assign data to second node
    second->next = third; 
     
    third->data = 30; //assign data to third node
    third->next = NULL;
 
    head = first;    //head pointing to the linked list
 
    printf("Before Reversed Operation: ");
    printLinkedList(head);
 
    head = reverseLinkedlist(head);
    printf("\nAfter Reversed Operation: ");
   printLinkedList(head);
     
    return 0;
}

Output:-

Before Reversed Operation: 10 20 30
After Reversed Operation: 30 20 10

Note:-
Interestingly if requirement is only to print the linked list in reversed order, then it can be done in very few steps and no actual reassignment of pointer values is required, see the following function

struct node * printReverseLL(struct node *list)
{
	if(!list)
		return NULL;
	printReverseLL(list->next);
	printf("%d ", list->data);
}

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂

Recommended -