給定循環單調非遞減列表中的一個點，寫一個函數向這個列表中插入一個新元素 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/
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/4ueAj6
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
""" # 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
