Поиск узла пересечения двух связанных списков

Question

Как найти узел пересечения связанного списка?

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

1. А и В две связанные связанные списки
2. A1, A2 ... A7 и B1 .. B3 являются узлами в списке
3. список A и B пересекаются в A5.

Мы должны найти узел пересечения

Answer 1

Решение 1:

Для каждого узла в списке проверки, если следующий такой же, как и в другом списке.

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

Это имеет сложность, т * п

Решения 2 (Efficient):

• Find длина обоих списков (L1 и L2 соответственно).
• Найдите разность абс. Длины [abs (L1-L2)].
• Поездка к узлу, полученному из предыдущей разницы.
• Теперь начать проверку, если A-> Следующий такой же, как B-> следующая

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; 
    } 
}