708. Insert into a Sorted Circular Linked List

case 1: empty list
case 2: single node list
case 3: list has distinct min and max
- case 3.1: cur.val <= insertVal <= cur.next.val
- case 3.2: cur.val > cur.next.val (wrap-around point between max and min)
  - 3.2.1: insertVal >= cur.val
  - 3.2.2: insertVal <= cur.next.val
case 4: list has identical min and max -> constant value list
- can insert anywhere

Main challenges are

come up with diverse test cases
write concise solution that works for all test cases

// Test case 1:  insert(null, 1)
// Test case 2:  insert(1->null, 0)
// Test case 3:  insert(1->null, 1)
// Test case 4:  insert(1->null, 2)
// Test case 5:  insert(1->1->1->null, 0)
// Test case 6:  insert(1->1->1->null, 1)
// Test case 7:  insert(1->1->1->null, 2)
// Test case 8:  insert(1->1->3->3->null, 0)
// Test case 9:  insert(1->1->3->3->null, 1)
// Test case 10: insert(1->1->3->3->null, 2)
// Test case 11: insert(1->1->3->3->null, 3)

class Solution:
    def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
        insert_node = Node(insertVal)
        if not head:
            insert_node.next = insert_node
            return insert_node

        cur = head
        while True:
            # case 1: low -> insertVal -> high
            if cur.val <= insertVal <= cur.next.val:
                break
            # case 2: max -> insertVal -> min
            elif cur.val > cur.next.val and (insertVal >= cur.val or insertVal <= cur.next.val):
                break
            else:
                cur = cur.next
                # case 3: loop back so list with uniform value
                    # special case: single element points to itself
                if cur == head:
                    break

        insert_node.next = cur.next
        cur.next = insert_node
        return head

708. Insert into a Sorted Circular Linked List - cocoder39/coco39_LC GitHub Wiki