Sword finger offer II 029 Sorted circular linked list

The finger of the sword Offer II 029. Sorted circular linked list

【 analysis 】 Because the linked list is still in order after insertion , So we traverse the linked list , Find the first node larger than the element to be inserted , Just insert this element in front of this node , Add up to some details .

1. First, because I want to return head, So let's make a mark and save it head, Make Node dummy = head, then head When the cursor is used .

2. Because it needs to be inserted in front of a node , So you need the previous node of this node , Because only head, So we can't know head Of pre, So we put head When pre,head Of next Come and be head that will do .

3. But if we start with a much larger element than the one we want to insert , such as 5,7,0,2, Insert 1, We found that we ordered head 7( primary head5 Of next7) Already greater than 1 Of course. , however 1 It should not be inserted in 7 In front of . So in this case, we need to find the smallest head of the linked list , We found the head 0 One characteristic is his pre want >head, But it does not rule out 3,3,3,3 This situation , So we have to judge whether it is back dummy.

4. If the linked list is empty and there is only one node in the linked list, you need to pay extra attention .

Several special examples ：

[3,3,5]
0
[1]
0
[1]
2
[3,3,3]
0
[]
1

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
    public Node insert(Node head, int insertVal) {
        if(head == null){
            Node node =  new Node(insertVal);
            node.next = node;
            return node;
        }
        Node dummy = head;
        Node pre = dummy;
        head = head.next;
        if(insertVal < head.val){
            while(pre.val <= head.val && head != dummy){
                head = head.next; pre = pre.next;
            }
        }
        while(true){
            if(head.val > insertVal) break;
            head = head.next;
            pre = pre.next;
            if(pre.val > head.val) break;
            if(pre == dummy) break;
        }
        pre.next = new Node(insertVal, head);
        return dummy;
    }
}