Insert a node into a sorted doubly linked list - Hacker Rank Solution

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.

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

Insert a node into a sorted doubly linked list - Hacker Rank Solution

Node SortedInsert(Node head,int data) {
    Node n = new Node();
    n.data = data;
    if (head == null) {
        return n;
    }
    else if (data <= head.data) {
        n.next = head;
        head.prev = n;
        return n;
    }
    else {
        Node rest = SortedInsert(head.next, data);
        head.next = rest;
        rest.prev = head;
        return head;
    }
}

Insert a node into a sorted doubly linked list - Hacker Rank Solution