hackerrank Insert a node at a specific position in a linked list in javascript

HackerRank – Insert a node at a specific position in a linked list JavaScript Solution

by

Insert a node at a specific position in a 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 complexity.

Problem Statement

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node.

A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

Read full details and access the challenge on Insert a node at a specific position in a linked list | HackerRank

Solution

function insertNodeAtPosition(llist, data, position) {
    let newNode = new SinglyLinkedListNode(data);
    let head = llist, currPos = 0, prev;
    while (head) {
        if (currPos === position) {
            newNode.next = head;
            head = newNode;
            if (prev) prev.next = head;
            return llist;
        }
        prev = head;
        head = head.next;
        currPos++;   
    }
}

Time Complexity : O(n)

Space Complexity : O(1)

The way this code works is we have to traverse the linked list until we reach the intended position to add the new node.

First we declare our variable, the new node, head (copy of llist, we do this so we can modify head and still return llist, the original head node), current position, previous node (to add the ‘next’ reference later on).

Now, we traverse through the linked list with a while loop for as long as head is not null or undefined. In every loop, we check if it is the intended position. If it is, we assign the current head node as the new node’s next node and we also assign the new node as the previous node’s next node, then we return the llist or original head node. Else, we update the previous node and the head node as well as the current position.

We have a while loop and no extra array in this solution, so we have O(n) time and O(1) space complexity.

Conclusion

That’s how you can solve the Insert a node at a specific position in a linked list Challenge in HackerRank.

This is a good challenge to practice your basics on linked lists in JavaScript.

If you have an 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 using JavaScript in this blog!

See you next post!

Leave a Comment