hackerrank Merge two sorted linked lists in javascript

HackerRank – Merge two sorted linked lists Solution in JavaScript

by

Merge two sorted linked lists 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(n) space.

Problem Statement

Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty.

Read full details and access the challenge on Merge two sorted linked lists | HackerRank

Note

First of all, let me say beforehand that there’s better solution than mine. I believe you can achieve O(1) space with recursion, but my solution uses a new linked list so it is O(n) space. But, my solution is easier to understand although it can be further optimized.

So, do read through my solution and tell me in the comments if you’ve thought of a better solution be it more efficient or more readable.

Solution

function mergeLists(head1, head2) {
    let mergedList = new SinglyLinkedList();
    while (head1 || head2) {
        if (!head1) {
            mergedList.insertNode(head2.data);
            head2 = head2.next;
        } else if (!head2) {
            mergedList.insertNode(head1.data);
            head1 = head1.next;
        } else if (head1.data < head2.data) {
            mergedList.insertNode(head1.data);
            head1 = head1.next;
        } else {
            mergedList.insertNode(head2.data);
            head2 = head2.next;
        }
    }
    return mergedList.head;
}

Time Complexity : O(n)

Space Complexity : O(n)

This solution is simple, we just create a new linked list and traverse through the 2 linked lists and storing them into the new one with a sorted order.

First, we declare the new linked list that we’ll use to store the merged sorted elements.

Then, we’ll use a while loop that’ll continue as long as either list still has an element to traverse.

In the while loop, we have to first check if either head of the linked lists is null. If it is, we store the opposing linked list’s head and traverse that linked list. We do this to avoid error when accessing null value.

Next, we check which head is smaller and store the smaller head so we can get a sorted linked list.

Finally, we return the merged and sorted linked list.

The code seems repetitive, but I have to do it this way to avoid error when accessing null value. So, let me know in the comments if you can make the code less repetitive.

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

Conclusion

That’s how you can solve the Merge two sorted linked lists Challenge in HackerRank.

For me, this challenge is tricky as we have to deal with null properties which may cause an error. But, overall this as a good challenge and is open for various approaches.

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