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