public Node insert(Node head, int insertVal) {

Node newNode = new Node(insertVal, null);

if (head == null) {

newNode.next = newNode;

return newNode;

}

Node p = head;

boolean inserted = false;

do {

if (p == p.next || p.val == insertVal || (p.val < insertVal && p.next.val > insertVal) ||

(((p.val > insertVal && p.next.val > insertVal) || (p.val < insertVal && p.next.val < insertVal)) && p.next.val < p.val)) {

newNode.next = p.next;

p.next = newNode;

inserted = true;

break;

}

p = p.next;

} while (p != head);

if (!inserted) {

newNode.next = p.next;

p.next = newNode;

}

return head;

}

public Node insert2(Node head, int insertVal) {

Node newNode = new Node();

newNode.val = insertVal;

if (head == null) {

newNode.next = newNode;

return newNode;

}

Node p = head;

Node dec = null;

while (true) {

if (p.val <= insertVal && p.next.val >= insertVal) {

newNode.next = p.next;

p.next = newNode;

return head;

}

if (p.val > p.next.val) {

dec = p;

}

p = p.next;

if (p == head) break;

}

if (dec == null) dec = head;

newNode.next = dec.next;

dec.next = newNode;

return head;

}