Last Updated: 22 Jul, 2020
Intersection of Two Linked Lists
Easy
Asked in companies
You are given two Singly Linked Lists of integers, which may have an intersection point.
Your task is to return the first intersection node. If there is no intersection, return NULL.
Example:-
The Linked Lists, where a1, a2, c1, c2, c3 is the first linked list and b1, b2, b3, c1, c2, c3 is the second linked list, merging at node c1.
Input Format:
The input format contains three lines consisting of the front part of the first list, front part of the second list and the intersection part of the lists, respectively.
All lines contain the elements of the singly linked list separated by a single space and terminated by -1.
So the first line would contain
a1, a2, ...an, -1.
Similarly, the second line would contain
b1, b2, ...bm, -1.
Similarly, the third line would contain
c1, c2, ...ck -1.
Output format :
The only output line contains data from the first merged node if the correct node is returned. If there is no merging or incorrect answer, the output contains -1.
You don't have to print by yourself explicitly. It has been taken care of. You need to return the first merged node.
Approaches
- For each node in the first list, traverse the entire second list
- Check if any node in the second list coincides with the first list
- If it does, return that node
- If it doesn’t, return NULL
- Traverse the first list and store the address/reference to each node in a hash set/map/dictionary.
- Then check every node in the second list:
- If the address of the node of the second list appears in the hash set/map/dictionary, then the node is the intersection node
- If we do not find any address of the second list node in the hash set/map/dictionary then return NULL
- Calculate the length of both the lists, say len1 and len2
- Get the absolute difference of the lengths, diff = |len1 – len2|
- Now traverse the long list from the first node to ‘diff’ nodes so that from there onwards, both the lists have an equal number of nodes
- Then traverse both the lists in parallel and check whether a common node is reached (Note that getting a common node is done by comparing the address of the nodes, not the data)
- If yes, return that node
- If no, return null