- Prepare
- Interview Preparation Kit
- Linked Lists
- Inserting a Node Into a Sorted Doubly Linked List

# Inserting a Node Into a Sorted Doubly Linked List

# 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 at the proper location to maintain the sort.

**Example**

refers to the list

Return a reference to the new list: .

**Function Description**

Complete the *sortedInsert* function in the editor below.

sortedInsert has two parameters:

*DoublyLinkedListNode pointer head*: a reference to the head of a doubly-linked list*int data*: An integer denoting the value of the field for the*DoublyLinkedListNode*you must insert into the list.

**Returns**

*DoublyLinkedListNode pointer:*a reference to the head of 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**

**Sample Input**

```
STDIN Function
----- --------
1 t = 1
4 n = 4
1 node data values = 1, 3, 4, 10
3
4
10
5 data = 5
```

**Sample Output**

```
1 3 4 5 10
```

**Explanation**

The initial doubly linked list is: .

The doubly linked list after insertion is: