查找两个链表的交集节点

Question

如何找到链表的交集节点？

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

1. A 和 B 是两个链表
。
2. 答1， 答2...A7 和 B1..B3 是列表的节点
3. 列表 A 和 B 在 A5 处相交。

我们必须找到交叉点的节点

Answer 1

解决方案 1：

对于列表中的每个节点，检查下一个节点是否与另一个列表中的节点相同。

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

这具有 m*n 的复杂性

解决方案 2（高效）：

• 查找两个列表的长度（分别为 L1 和 L2）。
• 求出长度的腹肌差 [abs（L1-L2）]。
• 前往从先前差值获得的节点。
• 现在开始检查 A->next 是否与 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;  
    }
}