Inserting a value in sorted circular linked list

Inserting an item in sorted circular linked list is tricky. If the elements in the list are unique then there are 3 cases to consider:

Case I: The new element to be inserted falls between 2 elements in the list.

Case II: The new element is larger than all the elements in the list.

Case III: The new element is smaller than all the elements in the list.

For cases where list is empty or list has only 1 element, it doesn't matter where you insert the new node.

In the solution below I assume ascendingly sorted list and no duplicates are considered. It would be easy to extend the program for that but it would grow a bit complex. So I have only presented code for the simple case. I might post another version with all cases handled later.

//linked list node
struct LNode {
LNode(int val_):val(val_),next(0){}
int val;
LNode *next;
};
LNode* insert(LNode *list, int val) {

//construct new node for this value
LNode *newNode = new LNode(val);

//check if list has no item
if(list == 0){
newNode->next = newNode;
return newNode;
}
//check if list contains only one item
else if (list->next == list) {
list->next = newNode;
newNode->next = list;
return newNode;
}
LNode  *temp, *node = list;
node = node->next;
while(list != node) {

//Case I: val falls between 2 values in the list
if(val > node->val && val <>next->val){
break;

}
//case II: val is greater than all the values in the list
else if(val > node->val && node->next->val <>val) {
break;

}
//case III: val is smaller than all the values in the list
else if( val <>next->val && node->next->val <>val) {
break;
}
node = node->next;
}

temp = node->next;
node->next = newNode;
newNode->next = temp;

return newNode;
}

Handling duplicate values

Capability to handle duplicate values can easily be added to the above code by replacing greater than and less than in value comparisons by greater than equal to and less than equal to. The new conditions will be:

  //Case I: val falls between 2 values in the list
if(val >= node->val && val <>next->val){
break;

}
//case II: val is greater than all the values in the list
else if(val >= node->val && node->next->val <>val) {
break;

}
//case III: val is smaller than all the values in the list
else if( val <= node->next->val && node->next->val <>val) {
break;
}

When how the list is sorted is not known

When how the list is sorted is not known you can add similar conditions for descending sorted list. But first you need to determine how the list is sorted. The sorting order can be determined by traversing elements until we find 2 increasing(ascending) or decreasing (descending) numbers in sequence. Why two? Because with one you never know if it is at the end of the list where the element order reverses. But when list has 2 elements, you never know how the list is sorted. Consider for example list 1, 2 as circular (1->2->1), then you have no way of telling if it is sorted in ascending order or descending order. Same is the case when list has more elements but each of them have same value except one (e.g 1,1,1,1,1,1,1,3).