Inserting a Node Into a Sorted Doubly Linked List: Hackerrank Solution

Question:

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.

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.

Sample Input

1
4
1
3
4
10
5

Sample Output

1 3 4 5 10

Explanation

The initial doubly linked list is: 1 <-> 3 <-> 4 <-> 10 -> NULL

The doubly linked list after insertion is: 1 <-> 3 <-> 4 <-> 5 <-> 10 -> NULL

Solution:

 This solution to this problem is very simple. Here you are already given a pointer to the head node of a sorted doubly linked list and an integer which is to be inserted. 

STEPS:

• Insert the integer value in data.
• Take another variable newHead to store the current head of the Linked List.
• Firstly check if the list is already empty than directly point  the head to the data, return head and exit.
• If not than we will traverse the whole list until we reach to the end of the list(i.e. newHead.next != null) or if we get newHead.data >= data, if found than insert the new node(i.e. data) between the previous node(newHead.prev) and the current node(newHead).

The code is shared below.

 static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) {

        DoublyLinkedListNode newHead = head;

        // DoublyLinkedListNode prev = null;

         DoublyLinkedListNode node = new DoublyLinkedListNode(data);

        if(newHead == null ) 

        {

            

            head = node;

            

        }

        else if(newHead.data >= data)

        {   newHead.prev = node;

            node.next =  newHead;

            node.prev =  null;

            head = node;

            

        }

        else {

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

        {       //prev = newHead;

                newHead = newHead.next; 

        }

        //DoublyLinkedListNode node = new DoublyLinkedListNode(data)

        node.next = newHead.next;

        node.prev = newHead;

        newHead.next = node;

        if(node.next != null)

            node.next.prev = node; 

        }

        return head;

    }

Thanks for reading, hope it helps.