原文链接: https://leetcode-cn.com/problems/4ueAj6

中文题目

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 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]

 

提示：

• 0 <= Number of Nodes <= 5 * 10^4
• -10^6 <= Node.val <= 10^6
• -10^6 <= insertVal <= 10^6

 

注意：本题与主站 708 题相同： https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/

通过代码

高赞题解

其实就三种情况，

1. 在中间能够找到一个节点cur，满足cur->val<=val<=cur->next->val，直接插入即可
2. 找不到，则一定是所有的值都比它小或大，其实都会插入到边界跳跃点，即找到cur，满足val<=cur->next->val<cur->val(比最小的还小）或cur->next->val<cur->val<=val（比最大的还大）

因此其实就三个不等式，cur->val<=val, cur->next->val>=val, cur->next->val>=cur->val，三个式子中满足一个或三个时，cur即为插入点。

[cpp1]
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if(head==nullptr) {
            head = new Node(insertVal);
            head->next = head;
            return head;
        }
        auto 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;
    }
}

上面是异或写的，下面用if拆了一下，可能更清晰一点。

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if(head==nullptr) {
            head = new Node(insertVal);
            head->next = head;
            return head;
        }
        auto cur = head;
        while(cur->next!=head){
            if(cur->next->val<cur->val){
                if(cur->next->val>=insertVal) break;
                else if(cur->val<=insertVal) break;
            }
            if(cur->val<=insertVal&&cur->next->val>=insertVal) break;
            cur = cur->next;
        }
        cur->next = new Node(insertVal, cur->next);
        return head;
    }
}

## 统计信息
| 通过次数 | 提交次数 | AC比率 |
| :------: | :------: | :------: |
|    3878    |    12978    |   29.9%   |

## 提交历史
| 提交时间 | 提交结果 | 执行时间 |  内存消耗  | 语言 |
| :------: | :------: | :------: | :--------: | :--------: |