Sorted circular linked list

introduce

Given Cyclic monotone non decreasing list A point in , Write a function to insert a new element into the list insertVal , Make the list still cyclic ascending .
Given can be the pointer to any vertex in the list , Not necessarily a pointer to the smallest element in the list .
If there are multiple insertion positions that meet the conditions , You can choose any location to insert a new value , After insertion, the whole list remains in order .
If the list is empty （ The given node is null）, You need to create a circular sequence table and return this node . otherwise . Please return to the original given node .

Example

Input ：head = [3,4,1], insertVal = 2
Output ：[3,4,1,2]
explain ： In the diagram above , There is a three element loop sequence table , You get a value of 3 Pointer to the node of , We need to insert elements into the table 2 . The newly inserted node should be in 1 and 3 Between , After insertion , The whole list is shown in the figure above , Finally, return to the node 3 .

solution (C++)

This problem is a pointer to any vertex , So the first idea is to traverse down , If you find a node cur Satisfy cur->val <= insertVal <= cur->next->val , You can insert it directly ;
If you can't find it , It means that all values are smaller or larger than it , So this will be inserted into the boundary position .
Satisfy insertVal <= cur->next->val <=cur->val( The insertion value is smaller than the smallest )
perhaps insertVal >= cur->val >= cur->next->val( The insertion value is larger than the maximum )

/* // Definition for a Node. class Node { public: int val; Node* next; Node() {} Node(int _val) { val = _val; next = NULL; } Node(int _val, Node* _next) { val = _val; next = _next; } }; */

class Solution {
    
public:
    Node* insert(Node* head, int insertVal) {
    
        // Sentenced to empty 
        if(head == nullptr){
    
            head = new Node(insertVal);
            head->next = head ;
            return head ;
        }
        auto cur = head;
        while(cur->next !=head){
    
            // If the next node is smaller than the current node , Prove that the boundary position is reached （ The end boundary is the maximum ）
            if(cur->next->val < cur->val){
    
                // If the next node is greater than the insertion value , Prove that the insertion value is smaller than the minimum 
                if(cur->next->val >= insertVal) break;
                //  If the current node is less than the insertion value , Prove that the insertion value is greater than the maximum value 
                else if(cur->val <= insertVal) break;
            }
            // If the current node is less than the insertion value and the next node is greater than the insertion value , Then insert it into this position 
            if(cur->val <= insertVal && cur->next->val >= insertVal)
                break;
            // If the three conditions are not met, find the next one 
            cur = cur->next;
        }
        cur->next = new Node(insertVal,cur->next);
        return head;
    }
};