Finding node of intersection of two linked list

Question

How to find a node of intersection of a linked list?

     A1-->A2-->A3-->A4-->A5-->A6-->A7
                         ^
                         |
               B1-->B2-->B3

1. A and B are two linked linked lists
2. A1, A2...A7 and B1.. B3 are nodes of a the list
3. list A and B intersect at A5.

We have to find the node of intersection

Answer 1

Solution 1:

For every node in the list check if the next is same as that in the other list.

   if(A->next == B->next)
   {
      //nodes of interaction
   }

This has a complexity as m*n

Solution 2 (Efficient):

• Find length of both the lists (L1 and L2 respectively).
• Find the abs difference of the lengths [abs(L1-L2)].
• Travel to the node obtained from the previous difference.
• Now start checking if A->next is same as B->next

Answer 2

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int length1=0;
        int length2=0;

        ListNode head1 = headA;
        ListNode head2 = headB;
        while(headA!=null){
            length1++;
            headA = headA.next;
        }
        while(headB!=null){
            length2++;
            headB = headB.next;
        }
        int minus = length1-length2;
        int abs = Math.abs(minus);
        if(minus<0){
            int step=abs;
            while(step>0){
                head2 = head2.next;
                step--;
            }
        }else{
            int step=abs;
            while(step>0){
                head1 = head1.next;
                step--;
            }
        }
        if(head1==head2) 
          return head1;
        while(head1!=null&&head2!=null&&head1!=head2)
        {

              head1=head1.next;
              head2=head2.next;

        }
      return head1;  
    }
}