title: Insertion in sorted doubly linked list
body: <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>