CareerCup

@Thiyaneshwaran: Reversing the lists will not work
A->B->C->D->E
T->F->I->C->D->E

In these two lists, node C is the same memory location. Reversing list1 will make C point to B, breaking the link between C->I.

The correct solution will be to find the difference in length, skip those many nodes in the longer list. Start comparing the next addresses of the nodes in the lists. When there is a match that is when the intersection starts. In the example mentioned above, the difference in length is 1. Hence you start from F->next with A->next. I->next = B->next. That is when you conclude the intersection has started.

Let L1 and L2 be the two lists.
1)find len1 = L1.length, len2 = L2.length
2)reverse the list L1
3)find len3 = L2.length
4)len1 + len2 - 2x = len3 - 1;
5)Now "x" is the common portion of the Y formed by the two list.
6) Reverse back the list L1.
7)(len1 - x/2)th node in the list L1 is the starting point of the Y

@KBSorter
Exactly reversing "list1" will make "C point to B", but still "I points C"(we never touched list2).
So i can start from T(list2) and reach A(list1). This is exactly the "len3" i have mentioned in my previous post.
When we again reverse back list1, everything will be fine. C will point back to D. Already I points to C, so we have everything in place.

take two stacks a and b
push all the elements of ll a into stack a and ll b into stack b

till the intersection point stack a.pop() is equal to stack b.pop()

@Anonymous on Nov 10
Good and simple one

Thiyaneshwaran S
has done a great job, very nice mathematics to calculate the position

Another way of representing Thiyaneshwaran solution.

Image inverted tree

. A



.B   >   >  .C    >   >   .D

ACD and BCD are two list. Find BC or AC.

AC + CD = k1 ........(1)
BC+ CD = k2 ........(2)
After Reversing the list BCD to DCB,

. A



.B <   <       .C    <  <      .D

AC + BC = k3 .......(3)

Solving Equations for three variable in three equations, One can find AC / BC
AC + CD = k1 ........(1)
BC+ CD = k2 ........(2)
AC + BC = k3 .......(3)

Thanks
Ankush

Thiyanesshwaran, can you tell me why its len-x/2 and not len-x since you already computed x using l1+l2-2x?

@Anonymous on Nov 10
Nice Solution

If i'm reading this right, the intersecting node is the converging node. Beyond this node, both lists will have the same number of nodes. So, why can one not do this?

1. Find the length of both lists. 
2. Skip longer-shorter nodes on the longer list. (now both nodes are equal in length)
3. do the below

while (list1->next!=null && list2->next!=null) {
   if(address of list1->next == address of list2->next) break;
   list1 = list1->next;
   list2 = list2->next;
}

print the converging node. Additionally we could run counters for both lists and give the index of the converging node.

The question says don't make any value or address comparison. So i hope my previous solution is correct.

Alternative Approach:
1) Create a HashMap/Hash Set of Node address values.
2) Start From the head of LL1, and traverse each node, and insert the address of that node in Hash_map. Do this till the First List is exhausted.
3)Now start from head of LinkedList 2, For each node Address, check if the value is already present in hash map. If no then move to next node. If yes, then we have reached the Intersection point

Solution:

1.traverse and find the length of both the lists and now traverse biggest list with big_len-small_len and after that traverse both the list by 1 and you will find them meet at one point if they have any intersection.

2.Create a hashtable.traverse the first list and make entry into the hash table and now traverse the second list and find whether the entry has been already made or not.