3. Insert in a Sorted List

Given a sorted singly linked list and a data, your task is to insert the data in the linked list in a sorted way i.e. order of the list doesn't change.

Example 1:

Input:
LinkedList: 25->36->47->58->69->80
data: 19
Output: 19 25 36 47 58 69 80

Example 2:

Input:
LinkedList: 50->100
data: 75
Output: 50 75 100

Solution:

Edge case: Insertion in start Insertion in end

Node *sortedInsert(struct Node *head, int data)
{

    Node *p = head;
    Node *q = NULL;
    Node *temp =  new Node(data);


    while (p != NULL)
    {

        if (data < p->data)
        {
            if (q == NULL)
            {
                temp->next = head;
                head = temp;
            }
            else
            {
                temp->next = p;
                q->next = temp;
            }
            return head;
        }
        q = p;
        p = p->next;
    }
    
    if(p == NULL){
        q->next = temp;
    }
    return head;
}

Time Complexity: O(n)