Linked List: Count the number of rotations in sorted and rotated linked list

Problem Statement:

You are given a linked list, which is sorted and rotated by k steps.

Find the value of k.

Example:

1 -> 2 -> 3 -> 4 -> 5 -> 6

rotated LL:

5 -> 6 -> 1 -> 2 -> 3 -> 4

Solution Explanation:

Solution is to traverse a LL to check if the current node is greater than the next node.

If the conditions is true, then break the loop else increase the counter value by 1 and move to the next node

Time Complexity: O(n1)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

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


int solution(struct Node* head)
{
	int count = 0;

	int min = head->data;

	while (head != NULL) 
	{

		if (min > head->data)
			break;

		count++;

		head = head->next;
	}
	return count;
}

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

	newNode->data = data;

	newNode->next = (*head);

	(*head) = newNode;
}

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

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

	// 4 -> 3 -> 2 -> 1 -> 6 -> 5
	push(&head, 5);
	push(&head, 6);
	push(&head, 1);
	push(&head, 2);
	push(&head, 3);
	push(&head, 4);

	print_list(head);

	cout <<endl<< "Linked list is rotated at the element: ";

	cout << solution(head) << endl;

	return 0;
}

Output

4 3 2 1 6 5 
Linked list is rotated at the element: 1