Given a sorted circular linked list, the task is to insert a new node in this circular list so that it remains a sorted circular linked list.

Example 1:

Input:

(the first and last node is connected,

i.e. 4 --> 1)

data = 2

Output: 1 2 2 4

Example 2:

Input:

(the first and last node is connected,

i.e. 9 --> 1)

data = 5

Output: 1 4 5 7 9

1. There will be 3 cases in this question:

In this case, create a node with data x and store its address at head_ref.

Case 2: data of head node is greater than new node's data

In this case as well, new node will become head of list and previous head will be second node.

Case 3: if none of the prev is true

Locate a node whose data is greater than new data and insert new node right before it. In case no such node is found in the list, append new node at the end.

c++ implementation:

`Node *sortedInsert(struct Node *head, int data){    struct Node* current = head;    struct Node* new_Node = new Node(data);        // Case 1 of the above algo    if (current == NULL)    {      head=new_Node;      return head;    }        // Case 2 of the above algo    else if (current->data >= new_Node->data)    {        /* If value is smaller than head's value then        we need to change next of last Node */        while(current->next != head)            current = current->next;                current->next = new_Node;        new_Node->next = head;        return new_Node;    }        // Case 3 of the above algo    else    {        /* Locate the Node before the point of insertion */        while (current->next!= head &&            current->next->data < new_Node->data)        current = current->next;                new_Node->next = current->next;        current->next = new_Node;        return head;    }}`
Time Complexity: O(n)
darkmode