hackerrank Get Node Value in javascript

HackerRank – Get Node Value Solution in JavaScript

by

Get Node Value 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 pointer to the head of a linked list and a specific position, determine the data value at that position. Count backwards from the tail node. The tail is at position 0, its parent is at 1 and so on.

Read full details and access the challenge on Get Node Value | HackerRank

Note

I have 2 solutions for this challenge.

The first solution is by storing the linked lists into an array and accessing it later on.

The second solution is counting the length of the linked lists and the looping through the linked list again only until the intended position.

The first solution has O(n) space and the solution has O(1) space.

Both solutions are not that complex but the second solution has better performance but it uses 2 loops.

So, just choose which one is better for you.

O(n) Space Solution

function getNode(llist, positionFromTail) {
    let arr = [];
    while (llist) {
        arr.push(llist.data);
        llist = llist.next;
    }
    let positionFromHead = arr.length - positionFromTail - 1;
    return arr[positionFromHead];
}

Time Complexity : O(n)

Space Complexity : O(n)

In this solution, we loop through the linked list to store all the data into an array.

Then we can just return the array’s element with the index of position from head, which is the array’s length decreased by position from tail and 1 (to accommodate the zero-index system).

We’re using a while loop and an array to store the linked list so we have O(n) time and O(n) space complexity.

O(1) Space Solution

function getNode(llist, positionFromTail) {
    let pos = 0, length = 0, head = llist;
    while (llist) {
        length++;
        llist = llist.next;
    }
    let positionFromHead = length - positionFromTail - 1;
    while (pos !== positionFromHead) {
        pos++;
        head = head.next;
    }
    return head.data;
}

Time Complexity : O(n)

Space Complexity : O(1)

For this solution, we use 2 loops.

The first loop is to count the length of the linked list.

Then we get the position from head and we’ll loop until we reach that position to return the node at that position.

We managed to cut down the space complexity from O(n) to O(1) since we no longer use an array to store the linked list.

On the other side, we slightly increase our time complexity to O(2n) because we use 2 loops but it is still considered O(n).

So, we have O(n) time and O(1) space complexity.

Conclusion

That’s how you can solve the Get Node Value Challenge in HackerRank.

This is a good challenge to think creatively on linked lists problems since there are multiple ways you can solve this challenge.

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