/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node() {}
public Node(int _val,Node _next) {
val = _val;
next = _next;
}
};
*/
class Solution {
public Node insert(Node head, int insertVal) {
if(head == null){
Node newhead = new Node(insertVal,null);
return newhead;
}
Node pre = head;
Node cur = head.next;
while(cur != head){
if(insertVal >= pre.val && insertVal <=cur.val){
Node newnode = new Node(insertVal,null);
pre.next = newnode;
newnode.next = cur;
break;
}
else if(cur.val < pre.val && (insertVal <= cur.val || insertVal >= pre.val)){
Node newnode = new Node(insertVal,null);
pre.next = newnode;
newnode.next = cur;
break;
}
pre = cur;
cur = cur.next;
}
//恰好在head前插入，因为上面的while当 cur = head的时候退出了
Node newnode = new Node(insertVal,null);
pre.next = newnode;
newnode.next = cur;
return head;
}
}
