# Insert a node in the given sorted linked list.

Objective: Given a linked list in which nodes are sorted in ascending order. Write an algorithm to insert a given node into the linked list so that all the nodes in the list will maintain the sorted order.

Example:

```Given Linked List:  -> 2, Insert node: 6
New List:  -> 2 -> 6

Given Linked List:  -> 1 -> 2 -> 4 -> 6 -> 10, Insert node: 5
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10

Given Linked List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10, Insert node: 50
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10 -> 50
```

Approach:

• Base cases:
• If the list is empty then make the new node as head of the list and return head.
• If the head is greater than equal to the given node then add the given node at the front and make it head. Return head.
• Iterate the list until a node is found, where current.next node > given node, insert the given node just after current node.

Time Complexity: O(N)

Complete Code:

Output:

```Given Linked List: Linked list is Empty, Insert node: 5
New List:  -> 5
-----------------------------------------
Given Linked List:  -> 7, Insert node: 4
New List:  -> 4 -> 7
-----------------------------------------
Given Linked List:  -> 2, Insert node: 6
New List:  -> 2 -> 6
-----------------------------------------
Given Linked List:  -> 1 -> 2 -> 4 -> 6 -> 10, Insert node: 5
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10
-----------------------------------------
Given Linked List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10, Insert node: 50
New List:  -> 1 -> 2 -> 4 -> 5 -> 6 -> 10 -> 50
-----------------------------------------
```