In this article, I will discuss how to rotate a linked list by its n node. That means if an existing linked list is 1->2->3->4->5 and a user-entered 2 then the linked list should be modified to 3->4->5->1->2.
Note: The value of n should be less than the length of the linked-list.
Steps to rotate a single linked list
- Traverse the linked-list by n nodes.
- Keep nth node in TmpNode.
- After that traverse, traverse the linked-list till the end and assign the address of the first node to the last node.
- Assign address of (n+1)node to the head (start) pointer.
- Point nth node next to NULL.
Code to rotate linked-list
This code rotates the linked list as per the user’s choice.
/* Function to rotate linked list by n nodes */
void RotateALinkedList(NodePointer *pHead, int iNode)
{
int iCount = 0;
NodePointer Current = *pHead;
NodePointer TmpNode =NULL;
//Get the position of nth node
for(iCount = 1 ; ((iCount < iNode) && (Current!=NULL)) ; iCount++)
{
Current = Current->pNextNode;
}
if(Current == NULL)
{
return;
}
else
{
//nth Node
TmpNode = Current;
}
//Get the last node
while (Current->pNextNode != NULL)
{
Current = Current->pNextNode;
}
//Assign the address of first node to the last node
Current->pNextNode = *pHead;
//Now Last node become first node
*pHead = TmpNode->pNextNode;
// Current->pNextNode = RotateNode;
TmpNode->pNextNode = NULL;
}
If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.
Your free trial is waiting
Driver program to rotate the linked list
In this driver source code user create a linked list as per the choice. After the creation of the linked list, it asked the user to enter their choice to rotate the 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 rotate linked list by n nodes */
void RotateALinkedList(NodePointer *pHead, int iNode)
{
int iCount = 0;
NodePointer Current = *pHead;
NodePointer TmpNode =NULL;
//Get the position of nth node
for(iCount = 1 ; ((iCount < iNode) && (Current!=NULL)) ; iCount++)
{
Current = Current->pNextNode;
}
if(Current == NULL)
{
return;
}
else
{
//nth Node
TmpNode = Current;
}
//Get the last node
while (Current->pNextNode != NULL)
{
Current = Current->pNextNode;
}
//Assign the address of first node to the last node
Current->pNextNode = *pHead;
//Now Last node become first node
*pHead = TmpNode->pNextNode;
// Current->pNextNode = RotateNode;
TmpNode->pNextNode = NULL;
}
/* 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 beginning
//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
--------- --------- --------- --------- ---------
| 1 | --+--->| 2 | --+--->| 3 | --|---->| 4 | --+--->| 5 | 0 |
--------- --------- --------- --------- ---------
*/
//Print the created node
PrintTheList(head);
printf("Enter the nth Node = ");
scanf("%d",&iData);
//Check the user choice
if( iData <= iNumberNode)
{
RotateALinkedList(&head,iData);
//Print the created node
PrintTheList(head);
}
else
{
printf("\n\nPlease Enter Valid nth node\n");
}
//Free the allocated memory
FreeAllocatedMemory(&head);
return 0;
}
OutPut:
Recommended Post
- Introduction to Linked List.
- Rotate a Linked List.
- Linked List Insertion.
- Delete a Linked List node.
- Generic Linked List in C
- Write a function to reverse a linked list
- File handling in C.
- How to create dynamic array in C?
- 15 Common mistakes with memory allocation.
- How to access 2d array in C?
- A brief description of the pointer in C.
- How to use function pointer in C?
- How to use the structure of function pointer in c language?
- Replace the nested switch case using an array and function pointer.
- Implement state machine in C.
- Function pointer in structure.
- Pointer Arithmetic in C.
- Memory Layout in C.
- Union in C, A detailed Guide.
- typedef vs #define in C.
- Macro in C, with example code.