{"id":3915,"date":"2021-08-17T12:02:15","date_gmt":"2021-08-17T12:02:15","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3915"},"modified":"2022-11-30T04:49:04","modified_gmt":"2022-11-30T04:49:04","slug":"count-rotations-in-a-sorted-and-rotated-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/count-rotations-in-a-sorted-and-rotated-linked-list\/","title":{"rendered":"Count rotations in a sorted and rotated linked list"},"content":{"rendered":"

\"\"<\/p>\n

Several approaches exist in the programming world to solve this problem, some efficient and some not so efficient. Let us build the intuition to solve this problem brick by brick, by first discussing some simple methods, which are not so efficient. In this blog, we will see the problem number of rotations in a sorted linked list.<\/p>\n

How To Find Number Of Rotations In A Sorted Linked List<\/h2>\n

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.<\/p>\n

Let\u2019s try to understand the problem statement with help of examples.
\nSuppose the given list is:<\/p>\n

\"\"<\/p>\n

Let us first discuss what counting rotations in a sorted and rotated list means.
\nLet’s sort this given list. The sorted list is:<\/p>\n

\"\"<\/p>\n

Now, let’s remove the last two elements and add them to the front of the list, we will get:<\/p>\n

\"\"<\/p>\n

That\u2019s 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.<\/p>\n

Input:<\/strong><\/p>\n

\"\"<\/p>\n

Output:<\/strong> Linked list rotated elements: 2<\/p>\n

Explanation:<\/strong> 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.<\/p>\n

\"\"<\/p>\n

Let\u2019s take one more example, say if the given list is:<\/p>\n

\"\"<\/p>\n

If we sort this list, we will get a list:<\/p>\n

\"\"<\/p>\n

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:<\/p>\n

\"\"<\/p>\n

which is the same as the list which was given to us in the input.<\/p>\n

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.
\nNow, 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?
\nWe are going to use a linked list traversal and compare the elements. Let us look at this simple yet efficient approach.<\/p>\n

Approach To Find Number Of Rotations In A Sorted Linked List<\/h2>\n

Firstly, we have to notice that the values are not sorted now. Now, what caused this distortion?
\nA 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.
\nWe will keep comparing adjacent elements:<\/p>\n

    \n
  • If the current node value is lesser than or equal to the next node value, nothing changes.<\/li>\n
  • 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.<\/li>\n<\/ul>\n

    We will have to keep a counter variable which will be incremented till it doesn\u2019t reach the break condition. Let us have a look at the algorithm.<\/p>\n

    Algorithm To Find Number Of Rotations In A Sorted Linked List<\/h2>\n
      \n
    • Initialize the count variable with 0.<\/li>\n
    • One by one, keep comparing adjacent node values and increase the count.<\/li>\n
    • If, at any point, the current node value is greater than the next node value, break from the loop.<\/li>\n
    • Return the count.<\/li>\n<\/ul>\n

      Dry Run To Find Number Of Rotations In A Sorted Linked List<\/h3>\n

      \"\"<\/p>\n

      Code Implementation To Find Number Of Rotations In A Sorted Linked List<\/h2>\n\t\t\t\t\t\t