Inserting a Node Into a Sorted Doubly Linked List Hackerrank

Inserting a Node Into a Sorted Doubly Linked List Hackerrank

Given a reference to the head of a doubly-linked list and an integer, data, create a new Node object having data value data and insert it into a sorted linked list.

Complete the Node* SortedInsert(Node* head, int data) method in the editor below. It has two parameters:

head: A reference to the head of a doubly-linked list of Node objects.
data: An integer denoting the value of the data field for the Node you must insert into the list.
The method must insert a new Node into the sorted (in ascending order) doubly-linked list whose data value is datawithout breaking any of the list’s double links or causing it to become unsorted.

Note: Recall that an empty list (i.e., where head=null) and a list with one element are sorted lists.

Input Format

Do not read any input from stdin. Hidden stub code reads in the following sequence of inputs and passes head and data to the method:

The first line contains an integer, q, denoting the number of lists that will be checked. The 2.q subsequent lines describe the elements to insert into each list over two lines:

The first line contains an integer, n, denoting the number of elements that will be inserted into the list.
The second line contains n space-separated integers describing the respective data values that your code must insert into the list during each call to the method.
Output Format

Do not print anything to stdout. Your method must return a reference to the head of the same list that was passed to it as a parameter. The custom checker for this challenge checks the list to ensure it hasn’t been modified other than to properly insert the new Node in the correct location.

Sample Input

1
3
2 5 4
Sample Output

2 4 5
Explanation

We start out with an empty list. We insert a node with data=2. The list becomes head –> 2 –> null. We return head.
The head of the previously modified list is passed to our method as an argument. We insert a node with data=5. The list becomes head –> 2 –> 5 –> null. We return head.
The head of the previously modified list is passed to our method as an argument. We insert a node with data=4. The list becomes head –> 2 –> –> 5 –> 4 –>null. We return head.
Hidden stub code then prints the final list as a single line of space-separated integers.

SOlution

We can traverse the list from left to right and find a suitable position for the new node to insert. It is useful to first examine the different positions that the new node could end up in, and then we can analyse each of those cases independently.
1. Empty list
2. At the beginning of the list
3. Somewhere at the middle of the list
4. At the end of the list
In any of the four cases, we need to allocate memory for our new node and also assign its data. So we can do this common operation first.
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
Having done this, we now need to set this newNode’s next and prev pointers and possibly update some other node’s pointers to adjust this node’s position in the list. Now we will examine each of the cases separately.
Empty list – This is the trivial base case in which the list given is empty, and it is the first element to be inserted. So we can simply put its next and prev pointers to NULL and return this node as the head of the list.

At the beginning of the list – If the newNode is to be inserted at the beginning, then its next pointer should point to the current head, the prev pointer to NULL. Also, the head’s prev pointer has to be updated to point to this node. Finally, the node has to be assigned as the new head of the list.

Somewhere in the middle of the list – In this case, we will have to find two nodes in between which we can place this newNode. If we denote these as left and right respectively then,
left->data < newNode->data && right->data >= newNode->data

"""
 Insert a node into a sorted doubly linked list
 head could be None as well for empty list
 Node is defined as
 
 class Node(object):
 
   def __init__(self, data=None, next_node=None, prev_node = None):
       self.data = data
       self.next = next_node
       self.prev = prev_node

 return the head node of the updated list 
"""
def SortedInsert(head, data):
    node = Node(data)
    if head is None:
        return node
    currentNode = head
    while currentNode.next is not None:
        if node.data >= currentNode.data and node.data <= currentNode.next.data:
            currentNode.next.prev = node
            node.next = currentNode.next
            currentNode.next = node
            return head
        currentNode = currentNode.next
    node.prev = currentNode
    currentNode.next = node
    return head
/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
     Node prev;
  }
*/

Node SortedInsert(Node head,int data) {
  
    Node n= new Node();
    n.data=data;
    n.next=null;
    n.prev=null;
    
    if(head==null)
        return n;
    if(head.data > data)
        {
        
        n.next=head;
        head.prev=n;
        return n;
    }
    
    Node temp=head;
    
    while(temp.next!=null)
        {
           
         if(temp.next.data > data)
             {
             
               n.next=temp.next;
               n.prev=temp.next.prev;
               temp.next=n;
               n.next.prev=n;
               return head;
         }
        temp=temp.next;
        
    }
    
    temp.next=n;
    n.prev=temp;
    return head;
    
}
Node* SortedInsert(Node *head,int data)
{ 
   //reserve memory for this new node
   Node *newNode = (Node*) malloc(sizeof(Node)); 
   //Set the data of newNode as data
   newNode->data = data; 
   //Now we need to update the next and prev pointers of newNode -
   //based on its position
   if(head == NULL) {
       //Base case : If the list is empty
       newNode->next = NULL; //Set next and prev pointers as NULL
       newNode->prev = NULL;
       //This node now becomes the head node(the only node), so return it.
       return newNode;
   }
   if(head->data >= newNode->data) {
       //If the node's position is in the beginning of the list
       //set the next pointer of the newNode to point to the currentHead
       newNode->next = head; 
       newNode->prev = NULL; //Because it is the beginning of the list
       //Update the prev pointer of the current head to point to newNode
       head->prev = newNode; 
       //This node now becomes the head node, so make it.
       head = newNode;
   } else {
       //Find the position of the new node using a temporary current Node
       Node *current = head;
       while(current->next != NULL && current->next->data < newNode->data) {
           current = current->next;
       }
       //newNode lies between current and current->next
       newNode->prev = current;
       newNode->next = current->next;
       //It might happen that newNode's position is at the end. 
       //In that case we cannot update the current->next's (which is NULL) 
       //prev pointer
       if(current->next != NULL) {
           current->next->prev = newNode;
       }
       //Update the next pointer of current to point to this new node.
       current->next = newNode; 
   } 
   //Finally return the head pointer.
   return head;
}
/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
     Node prev;
  }
*/
Node SortedInsert(Node head,int data) {
    Node n = new Node();
    n.data = data;
    if (head == null) {
        return n;
    }
    else if (data <= head.data) {
        n.next = head;
        head.prev = n;
        return n;
    }
    else {
        Node rest = SortedInsert(head.next, data);
        head.next = rest;
        rest.prev = head;
        return head;
    }
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.