Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the cyclic list.
If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the cyclic list should remain sorted.
If the list is empty (i.e., given node is
null
), you should create a new single cyclic list and return the reference to that single node. Otherwise, you should return the original given node.
The following example may help you understand the problem better:
In the figure above, there is a cyclic sorted list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list.
The new node should insert between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.
1、题目描述¶
给定循环升序列表中的一个点，写一个函数向这个列表中插入一个新元素，使这个列表仍然是循环升序的。给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
如果有多个满足条件的插入位置，你可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
如果列表为空（给定的节点是 null），你需要创建一个循环有序列表并返回这个点。否则。请返回原先给定的节点。
下面的例子可以帮你更好的理解这个问题：
在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2。
新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3。
2、解题思路¶
- 由于是递增序列，因此只有一个逆序对存在，找出这个逆序对，定位最大值与最小值
- 如果插入值小于最小值或者大于等于最大值，将值插入到最大与最小中间
- 从最小值开始查找，找到第一个不大于插入值的节点，将值插入到该点后面