HackerRank – Reverse a doubly linked list Solution in JavaScript

Reverse a 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 the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list.

Note: The head node might be NULL to indicate that the list is empty.

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

Solution

function reverse(llist) {
    while (llist.next) {
        llist = llist.next;
    }
    let newHead = llist;
    while (llist) {
        // store the temporary prev
        let prev = llist.prev;
        // swap the references to reverse order
        llist.prev = llist.next;
        llist.next = prev;
        // continue to the next node
        llist = llist.next;
    }
    return newHead;
}

Time Complexity : O(n)

Space Complexity : O(1)

The key to solve this challenge is to just go to the end of the linked list, then iterate back to the head while swapping the references to reverse the order of the linked list. Finally, return the new head node of the reversed linked list.

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 Reverse a doubly linked list Challenge in HackerRank.

This is a nice challenge to train your knowledge about doubly linked lists.

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!