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 
using namespace std;

struct Node {
    int data;
    struct Node* next;
};
 
int countRotation(struct Node* head)
{
    // counter variable
    int count = 0;
    
    Node* curr=head;
 
    
    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;

    newNode->next = (*head);
 
   
    (*head) = newNode;
}
 

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

int main()
{
    struct Node* head = NULL;
    push(&head, 5);
    push(&head, 3);
    push(&head, 1);
    push(&head, 11);
    push(&head, 10);
 
    printList(head);
    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++;

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

    Node newNode = new Node();

    newNode.data = data;

    newNode.next = (head);

    (head) = newNode;
    return head;
}

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;

    head = push(head, 5);
    head = push(head, 3);
    head = push(head, 1);
    head = push(head, 11);
    head = push(head, 10);

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

    System.out.print(countRotation(head) +"\n");

}
}

Output

10 11 1 3 5
Linked list rotated elements: 2

Time Complexity: O(n), as no nested traversal is needed.
Space Complexity: O(1).

So, in this article, we have tried to explain the most efficient approach to count rotations in a sorted and rotated linked list. This is a simple question, but we have to prevent overflows while traversing through the linked list. It uses many of our basic concepts, and that is what makes this question quite an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Program To Reverse A Linked List Using Stack
Next post Java Program to search an element in a Linked List

Leave a Reply

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