Sorted insert for circular linked list

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:

LinkedList = 1->2->4

(the first and last node is connected,

i.e. 4 --> 1)

data = 2

Output: 1 2 2 4

Example 2:

Input:

LinkedList = 1->4->7->9

(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:

    Case 1: head_ref is NULL

                  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)