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:
- head: A reference to the head of a doubly-linked list of DoublyLinkedListNode objects.
- 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.
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.
Inserting a Node Into a Sorted Doubly Linked List: Hackerrank Solution
Reviewed by Kshitij
on
June 15, 2020
Rating:
No comments:
If you have any doubts please let me know.