Inserting a Node Into a Sorted Doubly Linked List HackerRank Solution

Inserting a Node Into a Sorted Doubly Linked List HackerRank Solution

In this Inserting a Node Into a Sorted Doubly Linked List HackerRank solution, 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

Inserting a Node Into a Sorted Doubly Linked List HackerRank solution

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in Python

def sortedInsert(llist, data):
    node = DoublyLinkedListNode(data)
    if data < llist.data:
        node.next = llist
        llist.prev = node
        return node
    else:
        if llist.next:
            node = sortedInsert(llist.next, data)
        llist.next = node
        node.prev = llist
        return llist

Problem Solution in Java

public static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode llist, int data) {
        DoublyLinkedListNode node = new DoublyLinkedListNode(data);
        if (llist.data > data) {
            node.next = llist;
            llist.prev = node;
            return node;
        } else {
            if (llist.next != null) {
                node = sortedInsert(llist.next, data);
            }
            llist.next = node;
            node.prev = llist;
            return llist;
        }


    }

Problem Solution in C++

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
    DoublyLinkedListNode* inserted_node = new DoublyLinkedListNode(data);
    DoublyLinkedListNode* prev_llist = nullptr;
   
    auto head = llist;
   
    while (llist) {
        if (llist->data >= data) {                            
            inserted_node->next = llist;
            if (!prev_llist) {
                inserted_node->prev = prev_llist;                
                return inserted_node;
            }
            else {
                prev_llist->next = inserted_node;
            }
            return head;
        }        
        prev_llist = llist;
        llist = llist->next;
    }    
   
    prev_llist->next = inserted_node;
       
    return head;
}

Problem Solution in JavaScript

function sortedInsert(llist, data) {
       let node = new DoublyLinkedListNode(data)
    
    if (!llist) return node
    if (data < llist.data) {
        llist.prev = node
        node.next = llist
        return node
    }
    
    node = sortedInsert(llist.next, data)
    llist.next = node 
    node.prev = llist
    return llist


}
Solve original Problem on HackerRank here. Checkout more HackerRank Problems