Inserting a Node Into a Sorted Doubly Linked List

Given a reference to the head of a doubly-linked list and an integer, , create a new DoublyLinkedListNode object having data value  and insert it into a sorted linked list while maintaining the sort.

Function Description

Complete the sortedInsert function in the editor below. It must return a reference to the head of your modified DoublyLinkedList.

sortedInsert has two parameters:

1. head: A reference to the head of a doubly-linked list of DoublyLinkedListNode objects.
2. data: An integer denoting the value of the  field for the DoublyLinkedListNode you must insert into the list.

Note: Recall that an empty list (i.e., where ) and a list with one element are sorted lists.

Input Format

The first line contains an integer , the number of test cases.

Each of the test case is in the following format:

• The first line contains an integer , the number of elements in the linked list.
• Each of the next  lines contains an integer, the data for each node of the linked list.
• The last line contains an integer  which needs to be inserted into the sorted doubly-linked list.

Constraints

Output Format

Do not print anything to stdout. Your method must return a reference to the  of the same list that was passed to it as a parameter.

The ouput is handled by the code in the editor and is as follows:
For each test case, print the elements of the sorted doubly-linked list separated by spaces on a new line

Solution :- 

static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) {          

           //14   134105

            DoublyLinkedListNode node = new DoublyLinkedListNode(data);

            if (head == null)

                head = node;

            else if (head.data >= data)

            {

                node.next = head;

                node.next.prev = node;

                head = node;

            }

            else

            {

                while (head.next != null && head.next.data < data)

                {

                    head = head.next;

                }

                node.next = head.next;

                if (head.next != null)

                {

                    if (node.next != null) 

                        node.next.prev = node;

                }

                head.next = node;

                node.prev = head;

            }

            while (head.prev != null)

            {

                head = head.prev;

            }

            return head;

    }