> For the complete documentation index, see [llms.txt](https://sisyphus.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sisyphus.gitbook.io/project/leetcode-notes/linked-list/708.-insert-into-a-cyclic-sorted-list.md).

# 708. Insert into a Cyclic Sorted List

```python
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next):
        self.val = val
        self.next = next
"""
class Solution(object):
    def insert(self, head, insertVal):
        """
        :type head: Node
        :type insertVal: int
        :rtype: Node
        1. find the first prev where prev.val <= Val < prev.next.val
        2. 
        1. find the first prev where prev.val > prev.next.val
            Add after prev
        """
        if head is None:
            rst = Node(insertVal, None)
            rst.next = rst
            return rst
        
        cur = head.next
        isFirst = True # nice, one point for xixi
        while(cur != head or isFirst):
            if insertVal >= cur.val and insertVal <= cur.next.val:
                nextNode = cur.next
                cur.next = Node(insertVal, nextNode)
                return head
            if cur.val > cur.next.val and (insertVal >= cur.val or insertVal <= cur.next.val): # 
                nextNode = cur.next
                cur.next = Node(insertVal, nextNode)
                return head
            cur = cur.next
            isFirst = False
        
        nextNode = cur.next
        cur.next = Node(insertVal, nextNode)
        return head
```

1. When there is no node in linked list: **The inserted Node should be linked to itself.**
2. pre.val <= insertVal <= next.val \[**前后都 <= / >= 可以保证连续相同数字间任意位置都可以再插一个该数字**，如果只有前或后有 <=/>= 则只会插在连续相同数字的头部或尾部，这样的话不会错但少了很多可能存在的插入情况]
3. pre.val > next.val, 严格大于，没有 = 时，**达到sorted 的尾部**；**两种情况需要插入**：a) val 比 pre 还大；b) val 比 pre.next 还小
4. cur == head，转了一圈还没有插入 & return，说明**circle 内均为同一个数字，插入任意位置即可**；因为要判断 cur == head 来确定是否循环一圈，**需要用 isFirst 来执行 first loop**