Home Linked List Write a program to insert a node in a sorted Linked List

# Write a program to insert a node in a sorted Linked List

0 comment

Question:

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

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

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
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
}

}

//helper functions
{
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;

}

{
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;

}

{
{
}
}

//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));

printf("Enter a number to insert in sorted list:- ");
int num;
scanf("%d",&num);