Rotating a Singly Linked List

I know three things will never be believed — the true, the probable, and the logical.

Logic the pure essence of writing code. I would like to share a Little story with you all. It was a one or two weeks ago I was sitting in an exam for Data Structures and Algorithms and me being someone who was not good with pointers. I did not understand how singly linked list worked. It was few weeks into the course and I was blank about Linked List and nodes. Yet here I was facing my first graded lab on Linked List and It was about rotating a Linked List. I tried to derive the logic for it But I just could not I had it in my mind but somehow I just could not implement it on the IDE. I tried to draw the solution then implement it But to no avail. I tried to ask other but they were blank too and could not think of a solution So I took help from “External sources” You know what I mean to get over the exam and did it. But my soul was not at peace How can I not think of a solution How did I just cheat in the most important subject of the semester and there I was back on the drawing board deriving the solution to the rotation of Singly Linked List. This time the solution just came to my mind not because I had already seen a solution it was completely different from that and that I had not truly understood the solution I had seen.

The Solution I would be showing is the one I derived from Point zero Now you might see some rookie mistake Or maybe you don’t see any. Lets start by creating our Node Class.

class node
{
private:
    int data;//creating variable for data
    node* next;//pointer for pointing to next Node

public:
    node()//default constructor for node
    {
        data = 0;//intitalizing data variable to zero
        next = NULL;//pointing to NULL
    }
    node(int data)//parameterized constructor for Node
    {
        this->data = data;//setting data to passed data
        next = NULL;//POINTING TO NULL
    }
    node* getnext()//THE ADDRESS OF THE NEXT VARIABLE WHICH THE OBJECT IS STORING
    {
        return next;
    }
    void setnext(node* ptr)//SET the address for the next node
    {
        this->next = ptr;
    }
    void setdata(int data)//set data of the current node
    {
        this->data = data;
    }
    int getdata()//get data of the current Node
    {
        return data;
    }

What this code is doing if you don’t Understand. We are creating a class node. Now I do want to mention you might see many implementation of this using struct Online on many platform I did it with class because I find it Simpler This way. So the code has 2 variables one is int type to store data the other One is a pointer of the class Node Type so it can store address of the next node in the linked list. It has a default constructor to initialize the variables the pointer is pointed to null because we cannot know what we will be pointing to before hand. Moving on we will create The Linked List Class.

class linkedlist
{
private:
    node* head;//node type pointer object

public:
    linkedlist()//default constructor for the linked list
    {
        head = NULL;//head is initialized with NULL;
    }
    void add(int data)//add data function
    {
        node* N = new node(data);//we create a new node
        if (head == NULL)//if head is found equal to NULL
        {
            this->head = N;//The new node is equal to head.
        }
        else
        {
            node* temp = head;//we create a temp variable and set it to head.
            while (temp->getnext() != NULL)//loop to reach end
            {
                temp = temp->getnext();//we keep moving node to the next node
            }
            temp->setnext(N);//we point the last node to the new node.
        }
    }
    void display()//Display function.
    {
        node* temp = head;//we create a node type pointer and point it to head.
        while (temp != NULL)//loop to reach end
        {
            cout << temp->getdata() << endl;//print data of the list
            temp = temp->getnext();//moving node to next node 
        }
    }
}

The Linked List class has a dynamic Node type object named Head. it has an Add function which adds a new node to the list with the desired element. If there is no head and the head is NULL we set the head=N. N here is the name of the NewNode that was created. In the else situation we go to the end of the list and point the last node to the New Node. Lets move to the rotate function now.

void rotate(int data)
    {
        int j = 0;//varible to track how much rotation we are performing
        while (j < data) {
            //while j is less than data. Data here is the number of rotation

            int i = 0;//i is way of variable to have one pointer on the second last node.
            node* temp = head;//node pointing to head that will go to end.
            node* prev = head;//node that will go till second last node.
            while (temp->getnext() != NULL)//iterating to the end of the Linked List.
            {
                if (i >= 1)//if i greater than or equal to one
                {
                    prev = prev->getnext();//we move prev to the next node.
                }
                temp = temp->getnext();//we move temp to next node
                i++;//i++ so we can get prev moving.
            }
            temp->setnext(head);//we point the last node to the head the first element.
            head = temp;//we set head as temp.
            prev->setnext(NULL);//and we set the next of second last node as NULL.
            j++;//j++ to perfom the number of rotation.
        }
    }

This is the culprit that were talking about for so long these few lines of code had me panicking. Now we will discuss how this works. My solution was if I can rotate the list function some how If I can figure out the logic for doing it once. All I have to do is repeat it the Number of times Required. we start with a int variable J and data is passed as the number of rotation to be done. now till j is less than data. The loop will keep repeating. Inside the loop is a whole another story. we initialize a variable I to so we can control the prev node type pointer.

The main logic is to have temp pointer iterate to the end of the list and keep the Prev pointer to the second last Node. After that we point the last node which is temp to the head node. Remember head node is already pointing to all other nodes in front. Then we set the Last node as head. Now Why did we keep track of the second last node with prev? That was because we need to point the second last node next to NULL because it was pointing to temp.

Now the two pointer temp and prev are pointing to head. Now while temp getnext() is not equal to NULL meaning the temp next is not pointing to NULL we keep going forward. inside if I Not greater than or equal to 1 we do not move the prev pointer forward but the I is moved forward once and i++ is dont at the end now I is one step forward and prev has started. Now I is in front and prev is behind. now we reach the end. Temp is pointed to head. head is set to temp and prev is pointed to NULL and J is incremented which means one iteration is completed.

First step is a basic list. In the second image we are pointing the last element to head. And in the third image we are setting the last element as head and setting the second last node which was prev to NULL.