LCR029.循环有序列表的插入

链接：LCR029.循环有序列表的插入
难度：Medium
标签：链表
简介：给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

题解 1 - cpp

• 编辑时间：2022-06-18
• 执行用时：8ms
• 内存消耗：7.9MB
• 编程语言：cpp
• 解法介绍：遍历，考虑小于最小值和大于最大值。

class Solution {
   public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            Node* ans = new Node(insertVal);
            ans->next = ans;
            return ans;
        }
        Node *p = head, *node = new Node(insertVal);
        if (p->next != head) {
            int nmin = INT_MAX, nmax = INT_MIN;
            do {
                nmin = min(nmin, p->val);
                nmax = max(nmax, p->val);
                p = p->next;
            } while (p != head);
            if (nmin >= insertVal || nmax <= insertVal) {
                while (p->val <= p->next->val && p->next != head) p = p->next;
            } else {
                while (!(p->val <= insertVal && p->next->val >= insertVal))
                    p = p->next;
            }
        }
        node->next = p->next;
        p->next = node;
        return head;
    }
};