Java program to find whether 2 linked lists intersect.

The basic idea when we get by looking the question is that if 2 linked lists intersect at some place, then their tails should be the same. First we need to traverse both the linked list and find both its length. Then compare the last elements. If this is not equal, we can return there itself saying that both linked lists are not the same.

If the length of one node is greater than second node, traverse those many positions of the first node to reach the second node. From that position, traverse both the nodes and check whether the nodes are same. If equal nodes are found, then break and return true. If no equal nodes are found, then return false.

I am writing only the function which checks the intersection of the loop. Refer - http://sujithforu.blogspot.com/2012/10/linked-list-implementation-in-java.html for implemention of linked list.

public static boolean loopIntersection(ListElement node1, ListElement node2)
{
if(node1==null || node2==null)
{
return false;
}
ListElement head1,head2;
head1=node1;
head2=node2;
int len1=0,len2=0;

//for finding the length of the loop
while(head1!=null)
{
len1++;
head1=head1.next;
}


while(head2!=null)
{
len2++;
head2=head2.next;
}

if(head1!=head2)
{
return false;
}

if(len1>len2)
{
int diff = len1-len2;
head1=node1;
head2=node2;
for(int i=0; i<diff;i++)
{
head1=head1.next;
}

for(int i=0;i<len2;i++)
{
if(head1==head2)
{
return true;
break;
}
}

return false;
}

else if(len1<len2)

{
int diff = len2-len1;
head1=node1;
head2=node2;
for(int i=0; i<diff;i++)
{
head2=head2.next;
}

for(int i=0;i<len1;i++)
{
if(head1==head2)
{
return true;
break;
}
}

return false;
}

else
{
head1=node1;
head2=node2;

for(int i=0;i<len1;i++)
{
if(head1==head2)
{
return true;
break;
}
}

return false;
}

return false;
}