Note:

一共会有三种情况：

Case 1: 要插入的点既不是最大值也不是最小值，在这个链表的中间

Case 2: 要插入的点小于链表的最小值且大于链表的最大值, 那么应该插在tail

Case 3: 链表的所有元素都是uniform values，那么随便插一个位置就行。但是我们依然要遍历完整个链表，因为这样才能确保所有元素都是uniform

corner case: head == null, insert new Node(value)

Key word:

在一个环形链表里插入一个新结点。

class Solution {
    public Node insert(Node head, int insertVal) {
        Node newNode = new Node(insertVal);
        if (head == null) {
            newNode.next = newNode;
            return newNode;
        }

        Node cur = head;
        while (cur.next != head) {
            if (cur.val <= cur.next.val) {
                if (insertVal >= cur.val && insertVal <= cur.next.val) {
                    break;
                }
            } else {
                if (insertVal >= cur.val || insertVal <= cur.next.val) {
                    break;
                }
            }
            cur = cur.next;
        }

        Node next = cur.next;
        cur.next = newNode;
        newNode.next = next;
        return head;

    }
}

Complexity Analysis:

TC: O(N); only visit all node once

SC: O(1);