Interview question: Find the intersection of two linked lists(corrupt)

So the question assumes that there are two linked lists with two heads h1 and h2 but they end in the same location. It's like a Y shape.

So our quest is now to find out the intersected node (red node). The linked lists can be of any length and need not necessarily have same number of nodes. So the above list can have 50 nodes and below only 5.

I had this question for an in person tech screen and since I do not know the answer/idea before it was pretty difficult for me. So here's how my brainstorming went

1. So the lists can be either like 5,4 or 4,4 or 4,5 nodes. So a simple approach of
   
   1. while(cur1!=cur2){
      

      cur1=cur1.next;
      

      cur2=cur2.next;
      

      }
      

      Would not work.
      

2. The only distinguishing factor for the red node is that it has two links pointing to it.
   
3. So if we can have a mechanism to identify the parent links of each node then we can find the red node
   
   1. Hence create a hash table with node and parent links
      
   2. But this approach would waste a lot of space and I know from gut feeling that this would not be an elegant solution.
      
   3. As expected my interviewer doesn't want this approach
      
4. Have two pointers one fast and one slow and try to find if they merge
   
   1. For this my interviewer said this is not a cycle detection problem.
      
   2. I knew that and I was just trying to get a feeling if it could work
      
5. Now I am desperate I mumbled something with bit vector and mapping each node to a bit vector
   
   1. Now he laughed sarcastically
      
6. I felt that this is not going my way at all but there is nothing at this stage than to try all the approaches that I come up with.
   
   1. How about finding the lengths and may be this could help
      
   2. As soon as I said this he asked me to write code for this.
      
      1. I was skeptical but as soon as I started writing code I realized the trick for this problem
         
7. We have to make sure that both heads are at the same distance from the intersection point
   
   1. With this insight I got the solution – traverse both lists and find lengths- lenght1, lenght2.
      
   2. Whichever is larger move it length1-length2 times.
      
   3. Now use the first code snippet to find the intersection.
      
8. After I wrote the code I said it was not clean and wanted to refactor because it has duplication and I didn't handle case where length1 is lesser than lenght2.
   
   1. He allowed me to do that and I got code in less than 10 lines! And two helper functions.
      
9. After I written code we discussed test cases and where the code would fail, for example if there is no intersection or one list ends prematurely.
   

Urgh! Though I was able to solve this problem I felt very uncomfortable during the interview process, I mean I was being insulted or smirked at when I am trying to brainstorm a solution. Well whatever I got the answer. I only wished that I knew the solution before as many folks on career cup did if nothing but to save the embarrassment. So here goes the code.

public
ListNode findIntersection(ListNode h1,ListNode h2){

if(h1==h2)//this also handles both null case

return h1;

if(h1==null ||h2==null)

return
null;

ListNode cur1=h1;

ListNode cur2=h2;

int length1=findLength(cur1);

int length2=findLength(cur2);

if(length1>length2)

cur1=moveList(h1,length1-length2);

else
if(length2>length1)

cur2=moveList(h2,length2-length1);

while(cur1!=cur2){

cur1=cur1.next;

cur2=cur2.next;

}

return cur1;

}

private ListNode moveList(ListNode h1, int times) {

for(int i=0;i<times;i++){

h1=h1.next;

}

return h1;

}

private
int findLength(ListNode cur1) {

int count=0;

while(cur1!=null){

count++;

cur1=cur1.next;

}

return count;

}

Update: So even after my heroic solving of this problem, I got rejected. Well I don't know what to say.

Also there are 6 approaches to solve this - http://exclusiveminds.com/2010/03/05/write-a-function-to-get-the-intersection-point-of-two-linked-lists/