This post is completed by 1 user
|Add to List
22. Find Intersection Point in Two Linked Lists
Objective: Given Two linked lists, check whether both lists intersect each other, if yes then find the starting node of the intersection.
An intersection point means the end of one linked list is linked with some node in another linked list and it forms a Y shape.
Input: Two Linked List Output: Intersection Node or point
- Find the length of both the linked lists say : aLen and bLen
- Find the lenDiff = (aLen ~ bLen)
- Now starting from the head, Traverse the longer linked list by lenDiff
- Now traverse both the lists at the same time
- During traversal, check if at any point both the list points the at same node, then we have found the intersection point, return
- If we reach the end of the link lists without meeting the condition at the previous step. then there is no intersection point.
- Take one linked list and join its both ends.
- Now for the second Linked List, the problem is reduced to Linked List cycle detection - Tortoise and Hare Algorithm.
- Starting point of the loop will be the intersection point.
List A : -1-10-20-30-40-50 -5-10-30-40-50 Intersection found at 30