[数据结构与算法]剑指 Offer II 029. 排序的循环链表

剑指 Offer II 029. 排序的循环链表：

题目链接 ：剑指 Offer II 029. 排序的循环链表

题目：给定循环升序列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。
给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

思路：

1、关键是寻找新节点的插入位置

2、细分问题，遍历链表，每次对当前节点值进行判断：
（1）首先判断cur.val>=cur.next.val
（2）insertVal>=cur.val大于最大值，不符合插入条件
（3）insertVal<=cur.next.val 小于最小值，无法插入
（4）insertVal处于两个值直接，可以插入

AC代码：

/*
// 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)
        {
            head=new Node(insertVal);
            head.next=head;
            return head;
        }
        Node cur=head;
        while(cur.next!=head)
        {
            if((cur.val<=insertVal)^(cur.next.val>=insertVal)^(cur.next.val>=cur.val))
            {
                break;
            }
            cur=cur.next;
        }
        cur.next=new Node(insertVal,cur.next);
        return head;
    }
}