Write a C program to create and reverse a circular linked list. Logic to reverse a circular linked list in C programming. How to reverse a circular linked list in C program.
Required knowledge
Linked list, Circular linked list, C programming, Pointer, Structures, Functions, Dynamic memory allocation
In previous posts we learned basics about Circular linked list. We learned how to create and traverse a circular linked list. In this post we will move further and will learn to reverse a circular linked list.
Logic to reverse a Circular Linked List
Logic to reverse a circular linked list is more or less similar to Singly linked list.
Read more how to reverse a singly linked list?
Let us suppose following is our circular list to reverse.
Below is step by step logic to reverse a circular linked list.
- Initialize three pointer variables,
last = head,cur = head->nextandprev = head. Whereheadis pointer to first node in the circular linked list.Move
headnode ahead. So, after above operations the list should look like.
- Move
headnode ahead i.e.head = head->next; - Link current node with previous node i.e.
cur->next = prev; - Make previous node as current node i.e.
prev = cur; - Make current node as head node i.e.
cur = head;After performing all above operations the list should look like.
- Repeat step 2 to 5 till
head != last.
- After linking all nodes in loop, link current node with previous node i.e.
cur->next = prev;
- Finally move
headnode at its position. Moveheadnode to last i.e.head = prev;
After reversal our final list is
Program to reverse a Circular Linked List
/**
* C program to reverse a Circular Linked List
*/
#include <stdio.h>
#include <stdlib.h>
/* Basic node structure */
struct node {
int data;
struct node * next;
};
/* Function declaration */
void createList(struct node **head, int n);
void displayList(struct node *head);
void reverseList(struct node **head);
int main()
{
int n, choice;
struct node *head = NULL;
/*
* Run forever until user chooses 0
*/
while(choice != 0)
{
printf("--------------------------------------------\n");
printf(" CIRCULAR LINKED LIST PROGRAM \n");
printf("--------------------------------------------\n");
printf("1. Create List\n");
printf("2. Display list\n");
printf("3. Reverse list\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter total node to create: ");
scanf("%d", &n);
createList(&head, n);
break;
case 2:
displayList(head);
getchar(); // Hold screen
getchar(); // Hold screen
break;
case 3:
reverseList(&head);
printf("List reversed.\n");
getchar(); // Hold screen
getchar(); // Hold screen
break;
case 0:
printf("Exiting from application");
exit(0);
break;
default:
printf("Error! Invalid choice. Please choose between 0-3");
}
printf("\n\n");
}
return 0;
}
/**
* Reverses a circular linked list.
*/
void reverseList(struct node **head)
{
// Temporary helper variables
struct node *prev, *cur, *next, *last;
// Cannot reverse empty list
if (*head == NULL)
{
printf("Cannot reverse empty list.\n");
return;
}
// Head is going to be our last node after reversing list
last = *head;
prev = *head;
cur = (*head)->next;
*head = (*head)->next;
// Iterate till you reach the initial node in circular list
while (*head != last)
{
*head = (*head)->next;
cur->next = prev;
prev = cur;
cur = *head;
}
cur->next = prev;
*head = prev; // Make last node as head
}
/**
* Creates a circular linked list of n nodes.
*/
void createList(struct node **head, int n)
{
int i, data;
struct node *prevNode, *newNode;
prevNode = NULL;
newNode = NULL;
/* Creates and links rest of the n-1 nodes */
for(i=1; i<=n; i++)
{
// Create a new node
newNode = (struct node *) malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
// Link the previous node with newly created node
if (prevNode != NULL)
prevNode->next = newNode;
// Move the previous node ahead
prevNode = newNode;
// Link head node if not linked
if (*head == NULL)
*head = newNode;
}
// Link last node with first node
prevNode->next = *head;
printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
}
/**
* Display node content of circular linked list
*/
void displayList(struct node *head)
{
struct node *current;
int n = 1;
// Nothing to print in list
if(head == NULL)
{
printf("List is empty.\n");
return;
}
current = head;
printf("DATA IN THE LIST:\n");
do
{
// Print current node
printf("Data %d = %d\n", n++, current->data);
// Move to next node
current = current->next;
} while (current != head);
}--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Reverse list
0. Exit
--------------------------------------------
Enter your choice : 1
Enter total node to create: 4
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40
CIRCULAR LINKED LIST CREATED SUCCESSFULLY
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Reverse list
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 10
Data 2 = 20
Data 3 = 30
Data 4 = 40
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Reverse list
0. Exit
--------------------------------------------
Enter your choice : 3
List reversed.
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Reverse list
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 40
Data 2 = 30
Data 3 = 20
Data 4 = 10
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Reverse list
0. Exit
--------------------------------------------
Enter your choice : 0
Exiting from application