hackerrank delete duplicate-value nodes from a sorted linked list in javascript

HackerRank – Delete duplicate-value nodes from a sorted linked list JavaScript Solution

by

Delete duplicate-value nodes from a sorted 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

You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty.

Read full details and access the challenge on Delete duplicate-value nodes from a sorted linked list | HackerRank

Solution

function removeDuplicates(llist) {
    let head = llist, prev, arr = [];
    while (llist) {
        if (arr.includes(llist.data)) {
            prev.next = llist.next;
        } else {
            prev = llist;
            arr.push(llist.data);
        }
        llist = llist.next;
    }
    return head;
}

Time Complexity : O(n)

Space Complexity : O(n)

For this solution, we make a copy of the head that we’ll return later, prev to store the previous node and arr as an array to store the unique node values.

Then, we iterate through the linked list with a while loop, don’t forget to use llist = llist.next to continue to the next iteration.

In the loop, we check if the current node value has been accessed before by checking if that value exists in our array that stores unique values.

If the value is not unique, we cut off the current node by assigning the next node as the previous node’s next, skipping the current node altogether.

If the value is unique or hasn’t been accessed before, we make that node as prev and store it into the array of unique values.

Finally, we return head.

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

Optimized Solution

function removeDuplicates(llist) {
    let head = llist, prev, curr;
    while (llist) {
        if (llist.data == curr) {
            prev.next = llist.next;
        } else {
            prev = llist;
            curr = llist.data;
        }
        llist = llist.next;
    }
    return head;
}

Time Complexity : O(n)

Space Complexity : O(1)

For this solution, we optimize the previous solution with a minor tweak. We just replace the array that we use to store the unique values with a variable curr to take note of what value we’re at.

Since we’re working with a sorted linked list, we can use a variable instead of an array. We just check if the current llist matches with the curr value and do the same thing as with previous solution.

I’ve seen other solutions that used nested loops, and I want to avoid that. Then, I came up with the idea to replace the array with a variable to cut down the space complexity to O(1).

Conclusion

That’s how you can solve the Delete duplicate-value nodes from a sorted linked list Challenge in HackerRank.

For me, this challenge is nice since it challenges me to think how to avoid nested loop and still make a O(1) space solution.

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