# Insert Node in the Sorted Linked List

## 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;
*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
}

//O(1) constant time
}

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
{
}
//Find insertion point and insert the node after it
else
{
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

struct LLNode* head1 = NULL;//Initial list has no elements