A point in a monotone nondecreasing list of a given cycle , Write a function to insert a new element into the list insertVal , Make the list still cyclic ascending .
Given can be the pointer to any vertex in the list , Not necessarily a pointer to the smallest element in the list .
If there are multiple insertion positions that meet the conditions , You can choose any location to insert a new value , After insertion, the whole list remains in order .
If the list is empty （ The given node is null）, You need to create a circular sequence table and return this node . otherwise . Please return to the original given node .
Example 1：
Input ：head = [3,4,1], insertVal = 2
Output ：[3,4,1,2]
explain ： In the diagram above , There is a three element loop sequence table , You get a value of 3 Pointer to the node of , We need to insert elements into the table 2 . The newly inserted node should be in 1 and 3 Between , After insertion , The whole list is shown in the figure above , Finally, return to the node 3 .
Example 2：
Input ：head = [], insertVal = 1
Output ：[1]
explain ： The list is empty. （ The given node is null）, Create a circular sequence table and return this node .
Example 3：
Input ：head = [1], insertVal = 0
Output ：[1,0]
Tips ：
0 <= Number of Nodes <= 5 * 10^4
-10^6 <= Node.val <= 10^6
-10^6 <= insertVal <= 10^6
Be careful ： This topic and the main station 708 The question is the same ： https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/
source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/4ueAj6
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
""" # 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':
node = Node()
node.val = insertVal
if head is None:
node.next=node
return node
L = head
while L.next != head:
if (L.val <= insertVal and insertVal <= L.next.val) or (L.val > L.next.val and insertVal < L.next.val) or (L.val > L.next.val and L.val < insertVal):
break
L = L.next
node.next = L.next
L.next = node
return head
