Insertion in sorted doubly linked list
<p>I am given the pointer to the head node of a sorted doubly linked list and an integer to insert into the list.I am told to create a node and insert it into the appropriate position in the list such that its sorted order is maintained. The head node might be NULL.</p>

<p>Sample Input</p>

<p>NULL , data = 2  </p>

<p>NULL &lt;-- 2 &lt;--> 4 &lt;--> 6 --> NULL  , data = 5</p>

<p>Sample Output</p>

<p>NULL &lt;-- 2 --> NULL</p>

<p>NULL &lt;-- 2 &lt;--> 4 &lt;--> 5 &lt;--> 6 --> NULL</p>

<p>I tried the above problem.But My program is terminating due to timeout.What am I doing wrong in the below code. Assume Node class and main function is already there. Many Thanks in advance!!</p>

<pre><code>Node SortedInsert(Node head,int data) {

    Node newn = new Node();

    newn.data = data;
    newn.prev=null;
    newn.next = null;

    Node ptr = head;
    Node nex=head.next;

    while(ptr!=null &amp;&amp; nex!=null) {
        if(ptr.data&lt;=newn.data &amp;&amp; nex.data&gt;=newn.data) {
            newn.next = nex;
            newn.prev = ptr;
            nex.prev = newn;
            ptr.next = newn;
        }            
        else {
            nex=nex.next;
            ptr=ptr.next;
        }
    }

    if(ptr!=null &amp;&amp; nex==null) {
        if(ptr.data&gt;=newn.data) {
            newn.next=ptr;
            ptr.prev=newn;
            newn.prev=null;
            head=newn;
        }
        else {
            ptr.next=newn;
            newn.prev = head;
        }
    }

    if(head==null) {
        head = newn; 
    }

    return head;

}
</code></pre>