708. Insert into a Cyclic Sorted List

"""
# 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