Cerinta completa

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:

Limbajul de programare folosit: cpp14

Cod:

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
    DoublyLinkedListNode* node = new DoublyLinkedListNode(data);
    if (!llist) return node;
    if (data <= llist->data) {
        node->next = llist;
        llist->prev = node;
        return node;
    }
    DoublyLinkedListNode* cur = llist;
    while (cur->next && cur->next->data < data) cur = cur->next;
    node->next = cur->next;
    node->prev = cur;
    if (cur->next) cur->next->prev = node;
    cur->next = node;
    return llist;
}

Scor obtinut: 1.0

Submission ID: 464654536

Link challenge: https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list/problem

Inserting a Node Into a Sorted Doubly Linked List