Insert into a Cyclic Sorted List

写的时候一直在纠结应该返回什么，但是貌似因为是cyclic的所以可以随便返回一个node
网上的解释都写的特别复杂，看半天没懂。这里有一个YouTube视频演示了他自定义的一个class，head一直指向的是最小值。https://www.youtube.com/watch?v=8y5tYB004ss

我的解法
思路是有两个References，prev和curr，找到满足条件的prev和curr以后把新点插在它们两个的中间
因为至少需要两个node，所以0 node 和1 node的情况都作为edge case讨论了
关键1
用curr 从 node.next 开始走一圈
起始状态
 tail          headnode     headnode.next
                   prev                  curr

因为while的退出条件是curr != headnode.next，所以最终停止时
 
 tail           headnode  
 prev           curr

保证了所有的可以插入的地方都遍历过了，如果到终止条件还没有插入，那么一定插入到tail和headnode之间


关键2
有duplicate的情况
譬如 2-> 2 -> 2-> 里面插入3 （或者插入2）
当prev == curr == x 的时候是可以随便插入的，所以第一次满足这个条件时候就插入
这个情况归在了(prev.val <= curr.val && prev.val <= x && curr.val >= x)里面

如果是插入3，那么3是全局最大，就应该找到满足prev.val > curr.val的跳跃点进行插入。
然而因为整个list里面的值都相等，不存在跳跃点，3就插入在了最后的tail和head之间
【这里不能改成prev.val >= curr.val】因为(prev.val > curr.val && (prev.val < x || curr.val > x))的判断后半部分是或的关系，容易造成一个点插在两个重复点之间。譬如

1 -> 2 -> 2 -> 4 ->
 此时3 就会错误地插在2 和 2 之间

关键3
判断完prev和curr的位置之后最后进行点的插入， 这样保证了edge case的处理

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param node a list node in the list
     * @param x an integer
     * @return the inserted new list node
     */
    public ListNode insert(ListNode node, int x) {
        // Write your code here
        //no node
        if (node == null) {
            node = new ListNode(x);
            node.next = node;
            return node;
        }
        //only one node
        if (node.next == node) {
            node.next = new ListNode(x);
            node.next.next = node;
            return node;
        }
        ListNode prev = node;
        ListNode curr = node.next;
       
        while (curr != node) {
            if (prev.val <= curr.val && prev.val <= x && curr.val >= x) {
               break;
            } else if (prev.val > curr.val && (prev.val < x || curr.val > x)) {
                break;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        prev.next = new ListNode(x);
        prev.next.next = curr;
        return curr;
    }
}