700535. Intersection of Two Linked Lists
Easy
Intersection of Two Linked Lists
Slug: intersection-of-two-linked-list
Difficulty: Easy
Id: 700535
Topic Tags: Linked List, Hash, Sorting, Data Structures, Algorithms
Company Tags: VMWare, Flipkart, Accolite, Amazon, Microsoft, 24*7 Innovation Labs, D-E-Shaw, Walmart, Komli Media, Taxi4Sure
Summary
Given two linked lists that intersect at some node, find the intersection point. The problem assumes that the intersection is not included in the linked list and is not part of either linked list.
The key concepts involved are linked lists and hash tables.
Detailed Explanation
To solve this problem, we first need to traverse both linked lists until we reach the end of either of them. Then, we create a hash table (in this case, a HashMap in Java) that maps each node's value to its corresponding node. Next, we start traversing one of the linked lists again and check for each node if it is present in the hash table. If it is, then we have found the intersection point.
Here is a step-by-step breakdown:
- Initialize two pointers (or iterators) at the beginning of both linked lists.
- Traverse both linked lists until you reach the end of either list. This will ensure that both lists are of equal length and that there is no remaining part left in either list after intersection.
- Create a HashMap to store node values as keys and their corresponding nodes as values.
- Start traversing one of the linked lists again, keeping track of its current position using an iterator or pointer.
- For each node in this second traversal, check if it is present in the HashMap. If it is, then that means you have found the intersection point, and you can stop the traversal.
- If you reach the end of the second linked list without finding any intersection points, it means there was no intersection between the two lists.
Optimized Solutions
Java
public Node getIntersectionNode(Node headA, Node headB) {
if (headA == null || headB == null)
return null;
HashMap<Node, Integer> map = new HashMap<>();
int lenA = 0;
int lenB = 0;
Node currA = headA;
Node currB = headB;
while (currA != null) {
map.put(currA, lenA);
lenA++;
currA = currA.next;
}
while (currB != null) {
if (map.containsKey(currB)) {
return currB;
}
lenB++;
currB = currB.next;
}
return null;
}