hackerrank reverse a linked list in javascript

HackerRank – Reverse a linked list Solution in JavaScript

by

Reverse 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.

Problem Statement

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.

Read full details and access the challenge on Reverse a linked list | HackerRank

Note

If you’ve read my other posts, you’d notice usually I have an intuitive solution and an optimized solution (if there is one).

But, for this challenge, both solutions are equal in their time and space complexities.

So, which method to use is up to your preference.

Iterative Solution

function reverse(llist) {
    let curr = llist, prev, next;
    while (curr) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Time Complexity : O(n)

Space Complexity : O(1)

In this iterative solution, we’ll use a while loop.

As we iterate through the linked list, we first store the curr.next value as next (or you can also name it temp because it is just temporary) since we need to replace the curr.next to prev (to point the current node to the previous node so we can reverse it).

Then, we keep track of the previous node by assigning the current value to it. We do this because we’ll assign it as curr.next value in the next iteration.

After that, we replace curr with the temporary next we saved before.

This will continue into a loop eventually reversing the whole linked list by replacing the next pointers one by one in each iteration.

Finally, after all the iterations are done, we return the new pointer to the head node which is prev. We don’t return curr because it’d be null since it is the last node’s next value at this point.

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

Recursive Solution

function reverse(llist) {
    let head = llist;
    if (llist.next) {
        head = reverse(llist.next);
        llist.next.next = llist;
        llist.next = null;
    }
    return head;
}

Time Complexity : O(n)

Space Complexity : O(1)

In the recursive solution, we’ll first go to the end of the linked list with recursion and go backwards.

In each recursion, we assign null as the next value and the the current value next’s next value and return a reference to the current node.

By going backwards and assigning values, we’ll eventually reverse our linked list.

For example, we have a linked list of 1->2->3, in each recursion, our linked list will be modified to :

  1. 1->2->3->null->3
  2. 1->2->null->2->3
  3. 1->null->1->2->3

Since our recursion stops if the next node is null, we’ll be returning the second 1 making our first 1 not counted because there’s a null in between. Now, we’ve reversed our linked list into 1->2->3.

We’re traversing through the linked list once and we use no extra data structure, so we also have O(n) time and O(1) space complexity.

Conclusion

That’s how you can solve the Reverse a linked list Challenge in HackerRank.

This is a good practice for linked lists and reversing a data structure.

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