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

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素insertVal，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1：
输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。


示例 2：
输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。

示例 3：
输入：head = [1], insertVal = 0
输出：[1,0]

• 难度：Medium

这里做题

一道链表模拟题。关键在于找到合适的插入位置。可以分为以下几种情况：

1. 空链表，创建一个节点，连接成循环链表返回即可
2. 链表的所有值都相等，这时哪里都是合适的插入位置
3. 链表值不等

具体做法为：

1. 判断head是否为null，若是，创建新的循环链表返回。
2. 扫描一次链表，记录最大值max和最小值min
3. 如果min==max，选择head后面插入insertNode
4. 否则，扫描找到最大值max对应的节点处。如果insertVal>=max || insertVal<=min，那么插入这后面。否则，从此开始遍历，找到正确插入位置，即满足p.val<=insertVal && p.next.val>=insertVal位置处

时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)

class Solution {
    public Node insert(Node head, int insertVal) {
        Node insertNode = new Node(insertVal);
        insertNode.next = insertNode;
        // 链表空时，新建一个返回
        if(head == null)    return insertNode;
        Node p = head.next;
        // 扫描一遍链表，记录最大最小值，看是否全部相等
        int max = head.val;
        int min = head.val;
        while(p != head){
            max = Math.max(max, p.val);
            min = Math.min(min, p.val);
            p = p.next;
        }
        // 如果链表全部相等，任意位置都是合法插入位置
        if(max == min){
            insertNode.next = head.next;
            head.next = insertNode;
            return head;
        }
        // 找到链表最大值位置
        while(p.val <= p.next.val){
            p = p.next;
        }
        // 如果插入值大于最大值或小于最小值，插入
        if(insertVal >= max || insertVal <= min){
            insertNode.next = p.next;
            p.next = insertNode;
        }else{  // 否则找到正确位置
            while(true){
                p = p.next;
                if(p.val <= insertVal && insertVal <= p.next.val){
                    break;
                }
            }
            insertNode.next = p.next;
            p.next = insertNode;
        }
        return head;
    }
}