[sword offer ii] sword finger offer II 029 Sorted circular linked list

subject

 The finger of the sword  Offer II 029.  Sorted circular linked list 
 A point in a monotone nondecreasing list of a given cycle , 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  1：


 

 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 .


 Example  2：

 Input ：head = [], insertVal = 1
 Output ：[1]
 explain ： The list is empty. （ The given node is  null）, Create a circular sequence table and return this node .
 Example  3：

 Input ：head = [1], insertVal = 0
 Output ：[1,0]
 

 Tips ：

0 <= Number of Nodes <= 5 * 10^4
-10^6 <= Node.val <= 10^6
-10^6 <= insertVal <= 10^6

Method 1： Traverse

• Find between two incrementing points
• Find the rotation point

        public ListNode insert(ListNode head, int insertVal) {
    
            if (head == null) {
    
                ListNode insertNode = new ListNode(insertVal);
                insertNode.next = insertNode;
                return insertNode;
            }
            ListNode cur = head;
            while (cur.next != head) {
    
                if (cur.val < cur.next.val) {
    
                    if (insertVal >= cur.val && insertVal <= cur.next.val) {
    
                        insert(insertVal, cur);
                        return head;
                    }
                }
                if (cur.val > cur.next.val) {
    
                    if ((insertVal < cur.val && insertVal < cur.next.val) || insertVal > cur.val) {
    
                        insert(insertVal, cur);
                        return head;
                    }
                }
                cur = cur.next;
            }
            insert(insertVal, cur);
            return head;
        }


        private static void insert(int insertVal, ListNode cur) {
    
            ListNode insertNode = new ListNode(insertVal);
            ListNode nxt = cur.next;
            cur.next = insertNode;
            insertNode.next = nxt;
        }