LC 0708 [M] Insert into a Sorted Circular Linked List - ALawliet/algorithms GitHub Wiki

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        node = Node(insertVal)  
        
        if not head:
            node.next = node # just loop it back to itself
            return node

        cur, nxt = head, head.next # 2 pointers
        
        while cur.next != head: # stop when prev at tail right before loop
            # Case1 [1 <= (2) <= 3]: 1 <- Node(2) <- 3 (insert at middle, single case)
            if cur.val <= node.val <= nxt.val:
                break
            
            # Case2 [3 < () or () < 1]: 3 -> 1 and (3 -> Node(4) -> 1 or 3 -> Node(0) -> 1) (insert at end, 3 cases)
            # if cur.val > nxt.val and (node.val > cur.val or node.val < nxt.val):
            if cur.val > nxt.val and (cur.val < node.val or node.val < nxt.val):
                break
            
            cur, nxt = cur.next, nxt.next # move both pointers

        # Insert node. (in between cur and nxt)
        cur.next = node
        node.next = nxt           
        
        return head

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        ins = Node(insertVal, head)
        
        # empty list
        if not head:
            ins.next = ins
            return ins
        
        cur = head 
        
        while True:
            #print(cur.val)
            
            cur_lte_nxt = cur.val <= cur.next.val
            cur_gt_nxt = cur.val > cur.next.val
            cur_lte_ins = cur.val <= insertVal ; ins_lte_nxt = insertVal <= cur.next.val
            
            # insert end, <= AND
            if cur_lte_nxt and (cur_lte_ins and ins_lte_nxt):
                #print('end')
                break

            # insert middle, > OR
            elif cur_gt_nxt and (cur_lte_ins or ins_lte_nxt):
                # print('mid')
                break
                
            # exhausted
            if cur.next is head:
                break
            cur = cur.next
        #print(cur.val)
                
        ins.next = cur.next
        cur.next = ins 
        
        return head

"""
# 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':
        ins = Node(insertVal, head)
        
        if not head: # edge case empty list just point to itself
            ins.next = ins
            return ins
        
        cur = head
        
        while True:
            # insert at end
            if cur.val <= insertVal <= cur.next.val:
                break
            # insert at middle
            elif cur.val > cur.next.val and (insertVal >= cur.val or insertVal <= cur.next.val):
                break
            # insert at head, edge case if all nodes are the same and we traversed the whole list without meeting the above conds
            elif cur.next is head:
                break        
            cur = cur.next
            
        ins.next = cur.next
        cur.next = ins
        
        return head