Intersection of Two Linked Lists.

We have two linked lists which are merged at some point. We need to find the intersection.

This shape is popularly known as Y-Shape intersection also.

Finding of intersection can be done by several methods. Some of them are listed in this excellent article.

We will discuss a simpler approach which works by getting the difference of the counts of elements in two lists and performs at O(m+n) with O(1) complexity.

Algorithm:

1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

It is simple to code this if this concept is understood. Give it a try.