In this article, we will see how to reverse a linked list in C.
For Example,
Input : 10->20->30->NULL Output : 30->20->10->NULL
We can reverse the linked list using two approaches.
- Iterative method
- Recursive method
Iterative method
This is the simplest way to reverse linked list, in which we iterate a loop throughout the linked list and change the direction of the link.
Image shows the first Iteration of the loop.
For Example:
// A simple C program to Reverse a Linked-List
#include<stdio.h>
#include<stdlib.h>
// Creating Node
struct Node
{
int iData;
struct Node *pNextNode;
};
// Define the new type Node type and Node pointer
typedef struct Node NodeType, * NodePointer;
/* Function to reverse the linked list */
void ReverseLinkedList(NodePointer *pHead)
{
NodePointer Prev = NULL;
NodePointer Current = *pHead;
NodePointer Next;
while (Current != NULL)
{
Next = Current->pNextNode;
Current->pNextNode = Prev;
Prev = Current;
Current = Next;
}
//Now Last node become first node
*pHead = Prev;
}
/* Paas the reference of the head pointer of a list and
an integer data. This function use to add the node at the End*/
int InsertNodeAtEnd(NodePointer * pHead, int iUserData)
{
int iRetValue = -1;
NodePointer pLastNode = NULL;
NodePointer pNewNode = NULL;
//Give the Address of first Node
pLastNode = *pHead;
// Call malloc to allocate memory in heap for the new node
pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL) //Check allocated memory
{
pNewNode->iData = iUserData; //put the desire Data
pNewNode->pNextNode = NULL; //Give the Address of first Node
iRetValue = 0; // Update the return value
}
// If there is no node in beginning
if(pLastNode == NULL)
{
*pHead = pNewNode;
}
else
{
// Find the address of last node
while( pLastNode ->pNextNode != NULL)
{
pLastNode = pLastNode ->pNextNode;
}
// Assign last node address
pLastNode ->pNextNode = pNewNode;
}
return iRetValue;
}
/* Paas the reference of the head pointer of a list. This function use
to free the all allocated memory*/
void FreeAllocatedMemory(NodePointer *pHead)
{
NodePointer pTmpNode = NULL;
NodePointer pFirstNode = NULL;
//Assign the Address of first node
pFirstNode = *pHead;
/*check if pFirstNode is NULL, then now list is empty,
so assign NULL to head and return.*/
while (pFirstNode != NULL)
{
/*Save the pFirstNode in a pTmpNode node pointer*/
pTmpNode = pFirstNode ;
/*Assign the address of next on your list*/
pFirstNode = pFirstNode->pNextNode;
//Free the allocated memory
free(pTmpNode );
}
//Assign NULL to the head pointer
*pHead = NULL;
}
// This function use to prints the data of the list from the begning
//to the given list.
void PrintTheList(NodePointer pNode)
{
//Clear the screen
printf("\nDisplay Linked List: \n\n");
while (pNode != NULL)
{
printf("\n %d\n",pNode->iData);
pNode = pNode->pNextNode;
}
printf("\n\n");
}
//Create a number of nodes
int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
int iData = 0;
int iRetValue = -1;
int iCount = 0;
NodePointer pNewNode = NULL;
for(iCount =0; iCount < iNumberofNode; iCount++)
{
/*Enter desire data*/
printf("\n\nEnter the Data = ");
scanf("%d",&iData);
if((*pHead) == NULL)
{
// Call malloc to allocate memory in heap for the first node
pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL) //Check allocated memory
{
pNewNode->iData = iData; //put the desire Data
pNewNode->pNextNode = NULL; //Give the Address of first Node
*pHead = pNewNode; /*Assign the address of
first node to the head pointer*/
iRetValue = 0; // Update the return value
}
}
else
{
//Add the Node at the End
iRetValue = InsertNodeAtEnd(pHead,iData);
}
}
return iRetValue;
}
/* Driver program to test above functions*/
int main(void)
{
int iNumberNode =0;
int iData = 0;
/*Start with the empty list */
NodePointer head = NULL;
printf("\n\nEnter the number of nodes = ");
scanf("%d",&iNumberNode);
//Create a linked list of three node
CreateLinkedList(&head,iNumberNode);
/*
pHead
|
|
|
v
--------- --------- ---------
| 10 | --+--->| 20 | --+--->| 30 | 0|
--------- --------- ---------
*/
//Print the created node
PrintTheList(head);
// Reverse a linked list
ReverseLinkedList(&head);
/*
pHead
|
|
|
v
--------- --------- ---------
| 0 | 10|<----| | 20 |<----| | 30 |
--------- --------- ---------
*/
//Print the created node
PrintTheList(head);
//Free the allocated memory
FreeAllocatedMemory(&head);
return 0;
}
OutPut:
If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.
Recursive method
Recursion is also another technique to reverse the linked-list. In recursion, we are used stack memory to reverse the linked list.
// A simple C program to Reverse a Linked-List
#include<stdio.h>
#include<stdlib.h>
// Creating Node
struct Node
{
int iData;
struct Node *pNextNode;
};
// Define the new type Node type and Node pointer
typedef struct Node NodeType, * NodePointer;
/* Function to reverse the linked list */
void ReverseLinkedList(NodePointer *pHead)
{
NodePointer Current = *pHead;
if(Current == NULL) //If there is no node in Linked list
{
return;
}
else
{
//Get the Address of Next Node
NodePointer Next = Current->pNextNode;
//Trace Till the Last Node
if(Next == NULL)
{
return;
}
//Call recursive function
ReverseLinkedList(&Next);
Current->pNextNode->pNextNode = Current;
Current->pNextNode = NULL;
(*pHead) = Next;
}
}
/* Paas the reference of the head pointer of a list and
an integer data. This function use to add the node at the End*/
int InsertNodeAtEnd(NodePointer * pHead, int iUserData)
{
int iRetValue = -1;
NodePointer pLastNode = NULL;
NodePointer pNewNode = NULL;
//Give the Address of first Node
pLastNode = *pHead;
// Call malloc to allocate memory in heap for the new node
pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL) //Check allocated memory
{
pNewNode->iData = iUserData; //put the desire Data
pNewNode->pNextNode = NULL; //Give the Address of first Node
iRetValue = 0; // Update the return value
}
// If there is no node in beginning
if(pLastNode == NULL)
{
*pHead = pNewNode;
}
else
{
// Find the address of last node
while( pLastNode ->pNextNode != NULL)
{
pLastNode = pLastNode ->pNextNode;
}
// Assign last node address
pLastNode ->pNextNode = pNewNode;
}
return iRetValue;
}
/* Paas the reference of the head pointer of a list. This function use
to free the all allocated memory*/
void FreeAllocatedMemory(NodePointer *pHead)
{
NodePointer pTmpNode = NULL;
NodePointer pFirstNode = NULL;
//Assign the Address of first node
pFirstNode = *pHead;
//If there is no node n linked list
if(pFirstNode == NULL)
{
printf("There is no node in linkd list\n");
return ;
}
/*check if pFirstNode is NULL, then now list is empty,
so assign NULL to head and return.*/
while (pFirstNode != NULL)
{
/*Save the pFirstNode in a pTmpNode node pointer*/
pTmpNode = pFirstNode ;
/*Assign the address of next on your list*/
pFirstNode = pFirstNode->pNextNode;
//Free the allocated memory
free(pTmpNode );
}
//Assign NULL to the head pointer
*pHead = NULL;
}
// This function use to prints the data of the list from the begning
//to the given list.
void PrintTheList(NodePointer pNode)
{
//Clear the screen
printf("\nDisplay Linked List: \n\n");
if(pNode == NULL)
{
return ;
}
else
{
while (pNode != NULL)
{
printf("\n %d\n",pNode->iData);
pNode = pNode->pNextNode;
}
}
printf("\n\n");
}
//Create a Linked List
int CreateLinkedList(NodePointer *pHead, int iNumberofNode)
{
int iData = 0;
int iRetValue = -1;
int iCount = 0;
NodePointer pNewNode = NULL;
for(iCount =0; iCount < iNumberofNode; iCount++)
{
/*Enter desire data*/
printf("\n\nEnter the Data = ");
scanf("%d",&iData);
if((*pHead) == NULL)
{
// Call malloc to allocate memory in heap for the first node
pNewNode = malloc(sizeof(NodeType));
if( pNewNode != NULL) //Check allocated memory
{
pNewNode->iData = iData; //put the desire Data
pNewNode->pNextNode = NULL; //Give the Address of first Node
*pHead = pNewNode; /*Assign the address of
first node to the head pointer*/
iRetValue = 0; // Update the return value
}
}
else
{
//Add the Node at the End
iRetValue = InsertNodeAtEnd(pHead,iData);
}
}
return iRetValue;
}
/* Driver program to test above functions*/
int main(void)
{
int iNumberNode =0;
int iData = 0;
/*Start with the empty list */
NodePointer head = NULL;
//Enter the numbers of node
printf("\n\nEnter the number of nodes = ");
scanf("%d",&iNumberNode);
//Create a linked list of three node
CreateLinkedList(&head,iNumberNode);
/*
pHead
|
|
|
v
--------- --------- ---------
| 30 | --+--->| 20 | --+--->| 10 | 0|
--------- --------- ---------
*/
//Print the created node
PrintTheList(head);
printf("\n\nLinked list after the reverse\n\n");
// Reverse a linked list
ReverseLinkedList(&head);
/*
pHead
|
|
|
v
--------- --------- ---------
| 0 | 30|<----| | 20 |<----| | 10 |
--------- --------- ---------
*/
//Print the created node
PrintTheList(head);
FreeAllocatedMemory(&head);
return 0;
}
OutPut:
