Question:

Write a program to insert a node in a given sorted Linked List.

Given List: 23 -> 32 -> 99 -> 101 -> 2222

Node to add:- 50

Output:- 23 -> 32 -> 50 -> 99 -> 101 -> 2222

To insert a node in a sorted Linked List, we need to perform a basic Linked List operation discussed in this post.

In the given post, we knew the position at which we had to insert the node. But in this case we need to find the position at which we have to insert the node.

To find the position, start traversing the list from the beginning and get to the point, where we need to insert the node. Then we can call the insert a node function.

We can implement this problem this way.

#include struct node { int data; struct node * next; }; //defining a function to insert in sorted list struct node * insertInSorted(struct node * head, int number) { //let us suppose the initial position to be zero int pos = 0; //always create a temporary variable as we should never loose //the List HEAD struct node * temp = head; //now we need to traverse the list until we reach the node whose value //is greater than the number input. //If the 3rd number is greater, that means we need to insert a new number //at the third position. while(temp != NULL) { if(temp->data > number) break; // if we get the node, means we have the position, break temp = temp->next; // the next node pos++; // increment the position } head = addAtPos(head, number, pos); // we can call our original made function return head; } //helper functions struct node * addAtPos(struct node *head, int number, int pos) { int initial_pos = 0; struct node * mover = head; while(initial_pos != pos) { mover = mover -> next; initial_pos++; } struct node * temp = (struct node*)malloc(sizeof(struct node)); temp -> data = number; temp -> next = mover -> next; mover -> next = temp; return head; } struct node * addElement(struct node *head, int number) { struct node * temp = (struct node*)malloc(sizeof(struct node)); temp -> data = number; temp -> next = NULL; struct node * temp2 = head; while(temp2 -> next != NULL) { temp2 = temp2 -> next; } temp2 -> next = temp; return head; } void printList(struct node * head) { while(head != NULL) { printf("%d ",head->data); head = head->next; } } //main function to test the code int main(void) { //creating a list with initial sorted elements struct node * listHead = (struct node*)malloc(sizeof(struct node)); listHead->data = 23; listHead->next = NULL; listHead = addElement(listHead, 32); listHead = addElement(listHead, 99); listHead = addElement(listHead, 101); listHead = addElement(listHead, 2222); printf("Enter a number to insert in sorted list:- "); int num; scanf("%d",&num); listHead = insertInSorted(listHead, num); printList(listHead); return 0; }

Enter a number to insert in sorted list:- 50

23 32 50 99 101 2222