Question

You're given the pointer to the head node of a ordered linked list, an integer to add to the list. Write a function that inserts a number in the the list preserving its order. If the head pointer contains a null pointer that indicates an empty list.

Function insertNode has the following parameters:

• head: a SinglyLinkedListNode pointer to the head of the list
• data: an integer value to insert as data in your new node

Function prototype:

• SinglyLinkedListNode* insertNode(SinglyLinkedListNode* head, int data)

Answer 1

I've used arrow arrow notation to reference data and next part for a node since it was not given in the question. The explanation for the code is done with the help of comments.

The function to insert number in a list by preserving its order would be written as

SinglyLinkedListNode* insertNode(SinglyLinkedListNode* head, int data){
// Making a new node to store the data and also a current node to keep track of head.
struct SinglyLinkedListNode* current;
struct SinglyLinkedListNode* newNode;
newNode -> data = data;
newNode -> next = null;
  
// Let us first take the case where head is null or the data is the smallest.
if(head==NULL || head -> data >= data){
// If that happens, we will make our newNode head.
newNode -> next = head;
head = newNode;
}
else {
// Or we keep for the element which is greater than our data and then we insert our element.
current = head;
while (current->next != NULL
&& current->next->data < newNode->data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
return head;
}

Please comment and let me know if you have any doubts.

Thank you.

Have a good day.