# Count rotations in a sorted and rotated linked list ### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this question, we are given a linked list. This linked list was sorted and then rotated by X elements. We have to find the value of X.

### Problem Statement Understanding

Let’s try to understand the problem statement with help of examples.

Suppose the given list is: Let us first discuss what counting rotations in a sorted and rotated list means.

Let’s sort this given list. The sorted list is: Now, let’s remove the last two elements and add them to the front of the list, we will get: That’s it. That is the question. In this explanation, we have rotated the sorted list by 2 elements. In the question, we are given a rotated list. We have to return the number of elements by which it was rotated.

Input: Output: Linked list rotated elements: 2

Explanation: We can see that if we add the first two elements to the end of the linked list, it becomes sorted. Hence, 2 rotations is the answer. Let’s take one more example, say if the given list is: If we sort this list, we will get a list: Now we can see that if in the sorted list we move the last 3 elements and add them to the front, we will get: which is the same as the list which was given to us in the input.

From this, we can say that the linked list, which was given to us in the input, was initially rotated by 3 elements. So our output will be 3.

Now, I think the problem statement is clear from the above examples. No try to think how you can approach this problem before moving to the approach in the next section?

We are going to use a linked list traversal and compare the elements. Let us look at this simple yet efficient approach.

### Approach

Firstly, we have to notice that the values are not sorted now. Now, what caused this distortion?

A few of the elements from the end of the sorted linked list were added to the start of the list. We can get a hint here.

We will keep comparing adjacent elements:

• If the current node value is lesser than or equal to the next node value, nothing changes.
• But, if the current value is greater than the next node value, it means that the order isn’t sorted from this point, so we have found the initial starting point of our previously sorted linked list, and we will break the loop.

We will have to keep a counter variable which will be incremented till it doesn’t reach the break condition. Let us have a look at the algorithm.

### Algorithm

• Initialize the count variable with 0.
• One by one, keep comparing adjacent node values and increase the count.
• If, at any point, the current node value is greater than the next node value, break from the loop.
• Return the count.

### Dry Run ### Code Implementation

```#include<stdio.h>
#include<stdlib.h>

struct Node {
int data;
struct Node* next;
};

int countRotation(struct Node* head)
{
// counter variable
int count = 0;

while(curr&&curr->next)
{
// Compare adjacent values
if(curr->data>curr->next->data)
{
count++;
break;
}
count++;
curr=curr->next;
}

return count;
}
void push(struct Node** head, int data)
{
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;

}

void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;

printf("\n");
printf( "Linked list rotated elements: ");
int ans = countRotation(head);
printf("%d ",ans);

return 0;
}
```
```#include <bits stdc++.h="">
using namespace std;

struct Node {
int data;
struct Node* next;
};

int countRotation(struct Node* head)
{
// counter variable
int count = 0;

while(curr&&curr->next)
{
// Compare adjacent values
if(curr->data>curr->next->data)
{
count++;
break;
}

count++;
curr=curr->next;
}

return count;
}

void push(struct Node** head, int data)
{
struct Node* newNode = new Node;

newNode->data = data;

}

void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}

int main()
{
struct Node* head = NULL;

cout << endl;
cout << "Linked list rotated elements: ";

cout << countRotation(head) << endl;

return 0;
}
```
```import java.util.*;

public class PrepBytes
{

static class Node {
int data;
Node next;
};

static int countRotation(Node head)
{

int count = 0;

int min = head.data;

while (head != null) {

if (min > head.data)
break;

count++;

}
return count;
}
static Node push(Node head, int data)
{

Node newNode = new Node();

newNode.data = data;

}

static void printList(Node node)
{
while (node != null) {
System.out.printf("%d ", node.data);
node = node.next;
}
}

public static void main(String[] args)
{

Node head = null;

System.out.println();
System.out.print("Linked list rotated elements: ");

}
}
```
```class Node:

def __init__(self, data):
self.data = data
self.next = None

count = 0
while (head != None):
if (min > head.data):
break

count += 1

return count

newNode = Node(data)
newNode.data = data

def printList(node):

while (node != None):
print(node.data, end = ' ')
node = node.next

if __name__=='__main__':

print()
print("Linked list rotated elements: ",end = '')