C program to reverse a Circular Linked List

Quick links

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.

How to reverse a circular linked list

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.

Let us suppose following is our circular list to reverse.
Circular linked list

Below is step by step logic to reverse a circular linked list.

  1. Initialize three pointer variables, last = head, cur = head->next and prev = head. Where head is pointer to first node in the circular linked list.

    Move head node ahead. So, after above operations the list should look like.

    Circular linked list reverse step 1

  2. Move head node ahead i.e. head = head->next;
  3. Link current node with previous node i.e. cur->next = prev;
  4. Make previous node as current node i.e. prev = cur;
  5. Make current node as head node i.e. cur = head;

    After performing all above operations the list should look like.

    Circular linked list reverse step 2

  6. Repeat step 2 to 5 till head != last.
    Circular linked list reverse step 3

    Circular linked list reverse step 4

  7. After linking all nodes in loop, link current node with previous node i.e. cur->next = prev;

    Circular linked list reverse step 5

  8. Finally move head node at its position. Move head node to last i.e. head = prev;

    Circular linked list reverse step 6

After reversal our final list is
Circular linked list reversed

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);
}

Output

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

Happy coding 😉

About Pankaj

Pankaj Prakash is the founder, editor and blogger at Codeforwin. He loves to learn new techs and write programming articles especially for beginners. He works at Vasudhaika Software Sols as a Software Design Engineer and manages Codeforwin. In short Pankaj is Web developer, Blogger, Learner, Tech and Music lover.

Follow on: Facebook | Twitter | Google | or

Comments and discussion
Have a doubt, write here. I will help my best.
Before commenting you must escape your source code before commenting. Paste your source code inside
<pre><code> ----Your Source Code---- </code></pre>