Reverse a Circular Linked List

Today we will be discussing how to find reverse of a circular linked list. But, if are unfamiliar with the concepts of circular linked list then click on this link where I have explained everything about circular linked list from basic to advance. Suppose you have a circular linked list like 1->2->3->4->5 and 5 pointing to 1 again. then the reverse of this list will be 5->4->3->2->1 and then 1 pointing to 5 again. Let's see the procedure for reversing this kind of list:

Procedure

1. First we will make a circular linked list.

2. Now we will assign 3 pointers to the first 3 nodes of the list. Because, we have to reverse the links between 2 nodes and when we will reverse the link between 2 nodes then the node which is ahead will lose its link to the next node and we will not be able to go to the next node. SO that's why we need an extra pointer pointing ahead of current node.

Code

#include<iostream> using namespace std; struct node { int data; struct node* next; }; struct node* head=NULL; class linked { public: void insert(int x) { struct node* temp=new node(); temp->data=x; temp->next=NULL; if(head==NULL) { head=temp; } else { struct node* temp1=head; while(temp1->next!=NULL) { temp1=temp1->next; } temp1->next=temp; } } void assignhead() { struct node* temp=head; while(temp->next!=NULL) { temp=temp->next; } temp->next=head; } void reverse() { struct node* temp=head; struct node* prev=head; struct node* current=head; current=current->next; temp=temp->next->next; while(current!=head) { current->next=prev; prev=current; current=temp; temp=temp->next; } head=prev; current->next=head; } void disp() { struct node* temp=head; cout<<temp->data<<" "; temp=temp->next; while(temp!=head) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } }; int main() { linked l; l.insert(3); l.insert(5); l.insert(8); l.insert(1); l.insert(-2); l.insert(7); l.insert(-3); l.insert(11); l.insert(0); l.insert(6); l.assignhead(); l.disp(); l.reverse(); l.disp(); return 0; }

Explanation of Code

1. First we will write a simple code of circular linked list which will have 3 functions:

     - insert() - which will insert elements in the circular linked list.
     - assignhead() - to make a link between last and first node.
     - disp() - which will display the circular linked list.

2. Insert some values in the doubly linked list.

3. Now we have created a function named reverse() for reverse the circular linked list.
4. First we have created 3 pointer to node.
    struct node* temp=head;
    struct node* prev=head;
    struct node* current=head; 

5. Then we have assigned current to the second node and temp to the third node of the list. prev will be pointing to first node only.

6. Now we have started a loop which will execute until we reach the head or iterate the list once.

    while(current!=head)
    {

     ......

    }

7. Now we have assigned current->next to prev which means we have assigned the next node of current to prev.

    current->next=prev;

8. Then we have moved prev to current , current to temp and then we have incremented temp.

    prev=current;
    current=temp;
    temp=temp->next;

9. Then after the while loop we have assigned head to prev because head should now point to the last node after reversing .

    head=prev;

10. At last we have assigned current->next to head because current will now be at the first node and we have assigned next of current to head because this node will now become the last node. 

   current->next=head;