Find Merge Point of Two 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(n2) time and O(1) space.
Problem Statement
Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share a common node, return that node’s data value.
Read full details and access the challenge on Find Merge Point of Two Lists | HackerRank
Solution
function findMergeNode(headA, headB) {
while (headA) {
let temp = headB;
while (temp) {
if (temp == headA) return temp.data;
temp = temp.next;
}
headA = headA.next;
}
}
Time Complexity : O(n2)
Space Complexity : O(1)
The most straightforward solution that comes to mind is by using a nested loop.
First, we loop through the first linked list and inside that loop, we loop through the second linked list to compare both nodes. If they’re the same, we return that node’s data.
We’re using a nested while loop and no extra data structure so we have O(n2) time and O(1) space complexity.
Conclusion
That’s how you can solve the Find Merge Point of Two Lists Challenge in HackerRank.
This is an easy challenge, but I can only think of a quadratic time solution which is quite slow. Perhaps that’s the only way or there may be more effective solutions.
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!