## Insert a new node in the sorted linked list in sorted way

After inserting a node in sorted linked list the final linked list should be the sorted linked list.

### Example

## Algorithm

**a.** If linked list is empty linked list, then make the node as head and return it.

**b.** If value of node to be inserted is smaller than or equal to the head, then insert the node at start and make it head.

**c.** Traverse the linked list, find the node after which the input node to be inserted.

**d.** To find the node, keep track of previous and move forward in linked list.

**e.** If current node is greater than input, then previous is the node to be found.

**f.** Insert the node after it.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode* next;
};
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
if(*head == NULL)
*head=curr; //If this is first node make this as head of list
else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<"->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
void SortedInsertion(struct LLNode** head, struct LLNode* ToBeInserted)
{
struct LLNode* curr;
//Base cases
if (*head == NULL || (*head)->data >= ToBeInserted->data)
{
ToBeInserted->next = *head;
*head = ToBeInserted;
}
//Find insertion point and insert the node after it
else
{
curr = *head;
while (curr->next!=NULL && curr->next->data < ToBeInserted->data)
{
curr = curr->next;
}
ToBeInserted->next = curr->next;
curr->next = ToBeInserted;
}
}
//Main function
int main()
{
struct LLNode* head = NULL;//Initial list has no elements
insertAtBeginning(&head, 21);
insertAtBeginning(&head, 17);
insertAtBeginning(&head, 15);
insertAtBeginning(&head, 11);
insertAtBeginning(&head, 9);
insertAtBeginning(&head, 7);
insertAtBeginning(&head, 6);
insertAtBeginning(&head, 2);
cout<<"Input linked list is: ";
display(&head);
struct LLNode* head1 = NULL;//Initial list has no elements
insertAtBeginning(&head1, 8);
cout<<"Node to be inserted: ";
display(&head1);
//insering
SortedInsertion(&head, head1);
cout<<"\nOutput linked list: ";
display(&head);
return 0;
}
```