Insert value in sorted way in a sorted doubly linked list

Given a Sorted Doubly Linked List in ( non-decreasing order ) and an element x , the task is to insert the element x into the correct position in the Sorted Doubly Linked List.

Example:

Input: LinkedList = 3581012 , x = 9
Output: 35891012

Explanation: Here node 9 is inserted between 8 and 10 in the Doubly Linked-List.

Input: LinkedList = 141011 , x = 15
Output: 14101115

Explanation: Here node 15 is inserted at end in the Doubly Linked-List.

Approach :

• If the list is empty, new node becomes the head of the doubly linked list .
• else If the new node’s value is smaller than or equal to the head’s value , insert i t at the beginning.
• else, traverse the list to find the correct position where the new node’s value is greater than the current node and smaller than the next node. Adjust pointers to insert the node between the current and next node or after the current node (if curr’s next is NULL) .

                                                                                                                                                                           C

                                                                                                                                                                                     Java

                                                                                                                                                          Python

               C#

                                                                                                                                                                                    JavaScript

Output

3 5 8 9 10 12

Time Complexity: O(n) , where n is the number of nodes in the linked lsit.
Auxiliary Space: O(1)