How to rotate linked list by k nodes in C++

Hello Friends, Today we are going to learn how to rotate singly linked list by k nodes in a clockwise fashion in C++. I hope you know about the linked list and how it stores the data. So I am not going into that. Let’s start with an example and understand how to rotate and then we will see the code and then the algorithmic part.

Example:   Value = {1,2,3,4,5,6,7,9}

Suppose we have to rotate by 4 nodes.

Output : 5,6,7,9,1,2,3,4.

I don’t think there needs any explanation, how did I write the output. Let’s see the code.

C++ code for rotating linked list by k nodes

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};
Node *rotate(struct Node *head, int m);
void printList(Node *n);
void printList(Node *n)
{
    while (n != NULL)
    {
        cout<< n->data << " ";
        n = n->next;
    }
    cout<< endl;
}

int main()
{
        int n, value, r; // n = total number , r = rotate by r nodes
        cin>>n;
        
        cin>> value;
        Node *head = new Node(value);
        Node *tail = head;
        
        for(int i=0; i<n-1; i++)
        {
            cin>> value;
            tail->next = new Node(value);   // Suppose input is 1,2,3,4,5,6,7,9
            tail = tail->next;
        }
        
        cin>> r;
        
        head = rotate(head,r);
        printList(head);
    }
    return 1;
}

Node* rotate(Node* head, int m)
{
   Node* temp = head;
while(temp->next)
{
temp = temp->next;
}
temp->next = head; // linking last node with first node
Node *end;
while(m--)
{
end = head;
head = head->next;
}
end->next = NULL;
return head;
}
Output = 5,6,7,9,1,2,3,4

Understanding Algorithm

The algorithm is quite simple. First, make the linked list into the cyclic linked list by adding the address of the first node into the last node and then move the head pointer k number of times where k= rotate the linked list by k nodes. I used the while loop and move the head pointer and after that print from there.

You can visit the below link also.

Leave a Reply

Your email address will not be published. Required fields are marked *