Insertion into a cyclic sorted list with known head pointer of the smallest element

icsl_1.cpp

node* icsl_1(node* head, node* n) {
    if(!head) {
        // list is empty, set head to the new node.
        return (head = n->next = n);
    }

    node* cur=head;
    node* prev;
    
    // the new element is less than the smallest in the list
    if(n->key < head->key) {
        while(cur->next != head)
            cur=cur->next;
        n->next = head;
        return (head = cur->next = n);
    }

    // normal situation or new element is larger than the biggest
    do {
        prev = cur;
        cur = cur->next;
        if(n->value <= cur->value) break;
    } while (cur != head);

    n->next = cur;
    prev->next = n;
    return head;
}