C program to reverse a Circular Linked List

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.

Read more how to reverse a singly linked list?

Circular linked list

Let us suppose following is our circular list to reverse.

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

Circular linked list reversed

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