Insert Node into Sorted Circular Linked List

Write a function to insert a new value in a sorted Circular Linked List (CLL). For example, if the input CLL is following.

After insertion of 7, the above CLL should be changed to following

Solution:

Case 1: The new element to be inserted falls between 2 elements in the list.
Case 2: The new element is larger than all the elements in the list.
Case 3: The new element is smaller than all the elements in the list.

Case 4: List is empty.

Case 5: List has only one element.

Case 2 & 3 & 5 can be handled together, so we have 3 cases:

case1: pre.val<=x<=cur.val, insert between pre and cur.

case2: x is the minimum or maximum value, insert before head.

case3: traverse back to the starting point, insert before starting point

Time complexity is O(n), space complexity is constant space.

public static void insert(ListNode head, int x) {
  if(head == null) {  //list is empty
   ListNode node = new ListNode(x);
   node.next = node;
   head = node;
   return;
  }
  
  ListNode cur = head;
  ListNode pre = null;
  do {
   pre = cur;
   cur = cur.next;
   if(cur.val >= x && x >= pre.val) {  
    //case1: pre.val<=x<=cur.val, insert between pre and cur.
    break;
   }
   if((pre.val > cur.val) && (x < cur.val || x > pre.val)) {
    //case2: x is the minimum or maximum value, insert before head.
    break;
   }
  }while(cur != head);  //case3: traverse back to the starting point, insert before starting point
  
  ListNode newNode = new ListNode(x);
  newNode.next = cur;
  pre.next = newNode;
 }