This post is completed by 1 user

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

Example:

Approach:

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.

Trick Solution:

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.

Output:

List A :
-1-10-20-30-40-50
-5-10-30-40-50
Intersection found at 30