8.md

Sorted insert for circular linked list

Node* sortedInsert(Node* head, int data)
{
    Node* t = head;
    Node* p=head;
    Node* node = new Node(data);

    // Case 1: If the linked list is empty or the new node should be inserted at the beginning
    if(head == NULL)
    {
        node->next=node;
        return node;
    }
    else
    if(head->next == NULL)
    {
        if(data < head->data || data == head->data)       //insertion at first
        {
            node->next = head;
            head->next=node;
            head = node;
            return head;
        }
        else                                                //insertion at end
        {
            head->next = node;
            node->next=head;
            return head;
        }
    }
    else
    {
        Node* last;
        for(last=head;last->next!=p;last=last->next);      //insertion at first
        
        if(head->data> data)
        {
            node->next=head;
            head=node;
            last->next=head;
            return head;
        }
        // Case 2: Insert the new node at the correct position in the middle or end of the list
        while (t->next != p && t->next->data < data)
            t = t->next;

        node->next = t->next;
        t->next = node;
    }

    return head;
}