708. Insert into a Sorted Circular Linked List

──────────────────────────────────────────────────────────────────────

這個題目困難是一般來說，Linked List 是單向的，但是這裡有個循環，因此如果沒有處理好，就會造成無窮迴圈。

"""
# 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(insertVal)
        
        if not head:
            node.next = node
            return node
        
        prev = head
        curr = head.next
        
        while True:
            if prev.val <= node.val <= curr.val:
                break
            # last element
            if prev.val > curr.val:
                if node.val >= prev.val or node.val <= curr.val:
                    break
            
            prev = curr
            curr = curr.next
            if curr == head:
                break
                
        prev.next = node
        node.next = curr
        return head