Two linked lists A and B are joined on a particular node, called the point of intersection of the linked lists. Find the point of intersection, i.e. the first node after which both lists have same nodes.
Please try solving this problem before jumping on the solution
Click to learn
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
Naive Solution: Keep a node in List A as fixed and iterate over all nodes in List B to check if there is a node in List B same as the fixed node from List A. 1. Take two loops - outer loop for iterating over list A. Inner loop for list B. 2. In inner loop, check if a node matches current node of A. 3. If found, return the node, else move to next node. 4. If not found, return null.
Time Complexity: O(n*m) Space Complexity: O(1)
Solution using a Hash: 1. Iterate over first list and put the nodes in a hash set. 2. Iterate over other list and find the first node that is present in the hash set. This node is the intersection of the 2 lists.
Time Complexity: O(n+m) Space Complexity: O(n)
Support us by whitelisting IDeserve in your ad-blocker.