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);
    }
}