TEKPOOL

ashvin,

pl. think for a moment before you post.
let me take a very simple example:

[code:1]list 1: 1-2-3-4-6
list 2: 5-3-4-6[/code:1]

the intersection point being 3.

now if I start traversing the lists simultaneously till the second pointer reaches the end, the first pointer will be pointing to 6, which is definitely not the point of intersection.

Geekgod's method above works, but is slightly complicated to explain, spiyush's is simpler and faster

R

There is no need to reverse the link lists. All we need to do is to first calculate len=len1-len2 (len1>len2, as discussed above). Point p1 and p2 to list1 (the longer one) and list2 respectively. Then step only p1 for "len" no. of nodes. After this we are guaranteed that p1 and p2 are equidistant from the common node. So now start stepping p1 and p2 simultaneously until p1==p2. This will the common node. This is a simple O(n) solution.

got it !
then its possible with O(n^2) complexity with exhaustive search.
have any better option?

Hi!
I am Kallol from Bangladesh. I am newcomer here and this is my first post.
I think the question is little bit ambiguous.

It wanted the first occurance of the common node. But it didnt mention in thich list is under consideration. For example, here i have 2 lists

#1: 1->2->3->4->5->6->8->9->10
#2: 5->2->50->100

here , if i consider the first list , i will find the occurance of 2 in the 2nd list . So, 2 is the first occurance of the common node. But if i condsider 2 nd linked list I will find 5 as the first element which is common to both lists.

So, now which one doest the question asked.

If the both list has a unique common element it can be searched out in O(nlogn) complexity using binary search for each element of a list or in a process of trying to merge them.

Thank you.

I dont think that will work.. let say there List L1 has 15 nodes before it reaches teh intersection point after 25 nodes after that.. and list L2 has 100 nodes before it reaches the intersection point.. Then the len1=40 and len2=125 and len2-len1=85 and if you traverse the L1 85 times.. you will crash :)

Here's a solution:

Let list L1 have 'a' number of nodes leading to the intersecting node and 'k' number od nodes aftewards;

so a+k=len1 --> equation 1

Let list L2 have 'b' number of nodes leading to the intersecting node and 'k' number od nodes aftewards;

so b+k=len2 --> equation 2

You can calculate len1 and len2 by traversing the list

substracting the above 2 equations you get

a-b= len1-len2; --> equation 3

Now reverse List 2 and then traverse from the head of List 1 and count the number of nodes as you go, you will eventually reach the original head of List 2. Let the lenght you just computed be len 3

so a+b = len 3 --> equation 4

You have 2 equations (3 and 4) and 2 unknowns (a and b)

a and b are the lengths of list from the head of each list to the intersecting node.

You can re-reverse List L2 to revert it to the original state