Insert a node into a sorted doubly linked list

PROBLEM :

You’re given the pointer to the head node of a sorted doubly linked list and an integer to insert into the list. Create a node and insert it into the appropriate position in the list. The head node might be NULL to indicate that the list is empty.

Input Format
You have to complete the Node* SortedInsert(Node* head, int data) method which takes two arguments - the head of the sorted, doubly linked list and the value to insert. You should NOT read any input from stdin/console.

Output Format
Create a node with the given data and insert it into the given list, making sure that the new list is also sorted. Then return the head node of the updated list. Do NOT print anything to stdout/console.

Sample Input

NULL , data = 2
NULL <-- 2 <--> 4 <--> 6 --> NULL , data = 5

Sample Output

NULL <-- 2 --> NULL
NULL <-- 2 <--> 4 <--> 5 <--> 6 --> NULL

Explanation
1. We have an empty list, 2 is inserted.
2. Data 5 is inserted such as list remains sorted.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/*
    Insert Node in a doubly sorted linked list
    After each insertion, the list should be sorted
   Node is defined as
   struct Node
   {
     int data;
     Node *next;
     Node *prev;
   }
*/
Node* SortedInsert(Node *head,int data)
{
    Node *temp,*ptr ;
 
    temp=(Node*)malloc(sizeof(Node)) ;
    temp->data=data ;
    temp->next=NULL ;
    temp->prev=NULL ;
 
    if(head==NULL)
     {
        head=temp ;
        return head ;
    }
 
    if(head->data>=data)
        {
        temp->next=head ;
        head->prev=temp ;
        head=temp ;
     
        return head ;
    }
 
    ptr=head ;
    while((ptr->next!=NULL)&&(ptr->next->data<=data))
        ptr=ptr->next ;
 
    if(ptr->next==NULL)
        {
        ptr->next=temp ;
        temp->prev=ptr ;
     
        return head ;
    }
 
    temp->next=ptr->next ;
    ptr->next->prev=temp ;
    temp->prev=ptr ;
    ptr->next=temp ;
 
    return head ;
}


---------------------------------------------------------------------------------