hackerrank Inserting a Node Into a Sorted Doubly Linked List in javascript

HackerRank – Inserting a Node Into a Sorted Doubly Linked List JavaScript Solution

by

Inserting a Node Into a Sorted Doubly Linked List is a coding challenge with easy difficulty in the HackerRank data structures category. In this blog post, we’ll discuss how we can solve it in JavaScript in O(n) time and O(1) space.

Problem Statement

Given a reference to the head of a doubly-linked list and an integer, data, create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort.

Read full details and access the challenge on Inserting a Node Into a Sorted Doubly Linked List | HackerRank

Solution

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

Time Complexity : O(n)

Space Complexity : O(1)

We iterate through the linked list to first check if the data is less than the current node value. Then, we change the references (prev and next) and check for a few stuffs to return value according to the condition :

  • If there is a previous node, meaning it’s not the first node. If there is, we change the references of the previous node to the new node ad return the original head node.
  • If there are no previous nodes, meaning it is the first node. If this is the case, we return the new node.
  • If there’s no next node, meaning it is the last node. If this is the case, we add the new node as the last node and return the original head node.

We’re using a while loop and no extra data structure so we have O(n) time and O(1) space complexity.

Conclusion

That’s how you can solve the Inserting a Node Into a Sorted Doubly Linked List Challenge in HackerRank.

Even though it is actually basic data structure knowledge, it took me quite some thinking to come up with how to add a node (change the references) and with anticipating the edge cases (what if the new node is the largest or added as first node, etc). In the end, my solution is quite long but efficient enough.

If you have another approach different from mine, please do comment below!

Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript! We’ll also discuss more HackerRank solutions in JavaScript for the upcoming posts!

See you next post!

Leave a Comment