LCR 029. 循环有序列表的插入 (中等)

1，问题描述

LCR 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]

提示：

• 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/

2，初步思考

​ 使用步骤模拟来思考：

1. 如果 head 刚好小于 insertValue
   1. 如果存在大于 insertValue 的数据时，我们直接将数据插入到第一个大于 insertValue 数据之前即可
   2. 如果不存在在大于 insertValue 的数据，那么直接插入到下一个 loop 之前即可
2. 如果 head 大于 insertValue，找到下一个 loop 的开头
   1. 如果下一个 loop 的开头大于 insertValue，那么插入到他之前即可
   2. 如果下一个 loop 的开头小于 insertValue，那么问题转换为 1.1
3. 特殊的，有可能全部都是同一个数值，这个其实也是可以转换为 1，2 不影响，只不过需要把 head 当作一个基准，看看什么时候循环过来。

3，代码处理

import support.Node;

public class _LCR029循环有序列表的插入 {

    public Node insert(Node head, int insertVal) {
        Node tail = new Node(insertVal);
        if (head == null) {
            head = tail;
            head.next = head;
            return head;
        }

        Node newHead = new Node();
        newHead.next = head;
        while (true) {// 因为是一个环，所以直接true
            Node next = head.next;
            if (head.val <= next.val) {// 进行递增中
                if (head.val <= insertVal && insertVal <= next.val) {// 夹在中间即可
                    tail.next = next;
                    head.next = tail;
                    break;
                }
                if (head.next == newHead.next) {
                    tail.next = next;
                    head.next = tail;
                    break;
                }
            }
            if (head.val > next.val) {
                if (next.val > insertVal || head.val< insertVal) {// 不存在小于当前值的数据
                    tail.next = next;
                    head.next = tail;
                    break;
                }
            }

            head = head.next;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        _LCR029循环有序列表的插入 insert = new _LCR029循环有序列表的插入();
        Node node1 = new Node((1));
        Node node3 = new Node((3));
        Node node4 = new Node((4));
        node1.next = node3;
        node3.next = node4;
        node4.next = node1;
        Node node = insert.insert((node3), 2);
    }
}