给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。
首先想到的是逐个遍历，但是觉得有点简单，就是用排序加二分了。
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
"""
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
if head is None:
n = Node(val = insertVal)
n.next = n
return n
# 如果head不是最小的，那么肯定有分界点，使这个点左边（包含该点）是递增的，右边（不包含该点）也是
# 法一：建立递增数组，进行二分
arr_l = []
arr_r = []
node = head
arr_l.append(node)
if node.val <= node.next.val:
while node.next != head:
if node.next.val < node.val:
break
else:
arr_l.append(node.next)
node = node.next
if node.next != head:
node = node.next
while node != head:
arr_r.append(node)
node = node.next
arr = arr_r + arr_l
print([v.val for v in arr])
def val(node):
return node.val
i = bisect_left(arr, insertVal, key=val)
# print(i)
# print(arr[i].val)
node = None
if i == 0:
node = arr[-1]
else:
node = arr[i-1]
new_node = Node(val = insertVal, next=node.next)
node.next = new_node
return head
