Clockwise Rotation of a Linked List

Today we are going to discuss the algorithm for clockwise rotation of a linked list, but if you are new to linked lists then please refer to this link where I have explained everything about linked list. Let me explain you what is clockwise rotation of a linked list- Suppose we have a linked list 2->5->2->6->4->3. Then user enters an integer K=3. Now the linked list should rotate clockwise K times clockwise and we will get the linked list as 6->4->3->2->5->2.

Procedure

1. First we will make a linked list.

2. Now we will traverse the linked list. We will traverse the list till K times.

3. In each traversal we will remove the last node from linked list and insert it in the beginning of the list.

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 rotate(int k)
    {

        int c=0;
        while(c<k)
        {
            struct node* temp=head;
            struct node* x=NULL;
            while(temp->next->next!=NULL)
            {
                   temp=temp->next;
            }
            x=temp->next;
            temp->next=NULL;
            x->next=head;
            head=x;
            c++;
            disp();
        }


    }

    void disp()
    {
        struct node* temp=head;
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        cout<<endl;
    }
};

int main()
{
    linked l;
    l.insert(2);
    l.insert(5);
    l.insert(2);
    l.insert(6);
    l.insert(4);
    l.insert(3);
    l.disp();
    int n;
    cout<<"enter number of times you want to rotate the list: ";
    cin>>n;
    l.rotate(n);
    return 0;
}

Explanation of code(line by line)

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

- insert() - which will insert elements in the linked list.
- disp() - which will display the linked list.

2. Insert some values in the linked list.
3. Now we have created a function named rotate() to clockwise rotation of a linked list.

4. In the rotate() first we have created a variable 'c' which is initialized to 0. It will be variable which will keep track of the number of times we have to traverse the list.

5. Then we have created 'temp' which is a pointer to node variable initialized to head.

6. Then we have created 'x' which is another pointer to node variable which can store addresses of nodes only just like the head node.

7. Next we have started another while loop which will traverse from start till the second last node of the list.

while(temp->next->next!=NULL)
{
temp=temp->next;
}

8. Next we have stored the address of the last node of linked list in x with the help of temp->next (temp was the second last node from above while loop so its next will store the address of last node).

x=temp->next;

9. Then we have assigned temp->next = NULL because now temp->next will be the last node and last node points to NULL.

10. Then in x->next we have assigned value of head. x->next means the last node of linked list which was removed, will now point to the first node.

x->next=head;

11. Then in head we have stored address of x because now first node will be the last node which was removed and the address of last node was in x.

head=x;

12. Then c is incremented because first rotation is complete and next we will perform second rotation.

13. Then we have called disp() so that user can see the rotated linked list in each iteration.

Clockwise Rotation of a Linked List

Procedure

Code

Explanation of code(line by line)

Contact Form