Last Updated on November 30, 2022 by Prepbytes
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.
How To Find Number Of Rotations In A Sorted Linked List
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.
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 To Find Number Of Rotations In A Sorted Linked List
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 To Find Number Of Rotations In A Sorted Linked List
- 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 To Find Number Of Rotations In A Sorted Linked List
Code Implementation To Find Number Of Rotations In A Sorted Linked List
#include<stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* next;
};
int countRotation(struct Node* head)
{
// counter variable
int count = 0;
struct 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 = (struct Node*) malloc(sizeof(struct 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);
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;
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");
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
def countRotation(head):
count = 0
min = head.data
while (head != None):
if (min > head.data):
break
count += 1
head = head.next
return count
def push(head, data):
newNode = Node(data)
newNode.data = data
newNode.next = (head)
(head) = newNode
return head
def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next
if __name__=='__main__':
head = None
head = push(head, 5)
head = push(head, 3)
head = push(head, 1)
head = push(head, 11)
head = push(head, 10)
printList(head)
print()
print("Linked list rotated elements: ",end = '')
print(countRotation(head))
Output
10 11 1 3 5Linked list rotated elements: 2
Time Complexity To Find Number Of Rotations In A Sorted Linked List: O(n), as no nested traversal is needed.
Space Complexity To Find Number Of Rotations In A Sorted Linked List: O(1).
In this blog, we have tried to explain the most efficient approach to number of rotations in a sorted 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.
FAQ
1. What is a sorted list in data structure?
A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory.
2. What are the 4 types of linked list?
There are four key types of linked lists:
- Singly linked lists.
- Doubly linked lists.
- Circular linked lists.
- Circular doubly linked lists.
3. Is the linked list FIFO or LIFO?
A singly-linked list may be LIFO (last-in-first-out) or FIFO (first-in-first-out). If the list is using the LIFO method, the nodes will be added to and deleted from the same end. If it’s using FIFO, nodes will be added to one end and deleted from the opposite end. Additionally, the linked list may be sorted.