Insert into a Sorted Circular Linked List

给一个循环并且排序的linked list, 现在像往里面加一个node, 求加在哪里. 这个题要用双指针, 这样才能找到出现的前后node. 然后有三种情况, 第一种是正常的在最大和最小值中间的node, 这样的node直接接上去就可以了, 第二种是自己就是最大或者最小值. 第三种是环中所有值都一样, 这样很难判断环, 所以要单写出来当corner case.

/*
// 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 n = new Node(insertVal);
            n.next = n;
            return n;
        }
        Node prev = head;
        Node cur = head.next;
        boolean done = false;
        do {
            if(prev.val <= insertVal && insertVal <= cur.val) {
                done = true;
            } else if(prev.val > cur.val){ // at the end 
                if(insertVal <= cur.val || insertVal >= prev.val) {
                    done = true;
                }
            }
            
            if(done) {
                prev.next = new Node(insertVal);
                prev.next.next = cur;
                return head;
            }            // if not done
            else {
                prev = cur;
                cur = cur.next;
            }            
        } while(prev != head);
        
        // uniform value;
        prev.next = new Node(insertVal);
        prev.next.next = cur;
        return head;
    }
}