The first common node of two linked lists -- two questions per day

The finger of the sword Offer 52. The first common node of two linked lists

Brushing questions makes me happy

subject ： Enter two linked lists , Find their first common node .

Like the two linked lists below **：**

At the node c1 Start meeting .

Example 1：

 Input ：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 Output ：Reference of the node with value = 8
 Enter an explanation ： The value of the intersection node is  8 （ Be careful , Cannot be if two lists intersect  0）. Starting from the respective heads , Linked list  A  by  [4,1,8,4,5], Linked list  B  by  [5,0,1,8,4,5]. stay  A  in , There is... Before the intersection node  2  Nodes ; stay  B  in , There is... Before the intersection node  3  Nodes 

Ideas

The premise is to understand that the same node means that their node addresses are the same , It's not an element .

Use double pointers to solve , One The pointer On A Linked list , One The pointer stay B Linked list , The two pointers run separately , Calculate the respective lengths , Long minus broken , Get the difference （gad）, Let the long pointer go more first gab Step ,（ because 0 To gad The previous nodes must be different , Because we are not elements ）, Last Two pointers go together again , Compare... Together

public class  The first common node of two linked lists  {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
            ListNode left=headA;
            ListNode right=headB;
            int lenA=0;
            int lenB=0;
            while (left!=null){
    
               lenA++;
                left=left.next;
            }
           while (right!=null){
    
            right=right.next;
            lenB++;
          }
           left=headA;
           right=headB;
           int gad=0;
           ListNode temp=null;
           if (lenB>lenA){
    
               temp=left;
               left=right;
               right=temp;
               gad=lenB-lenA;
           }else {
    
               gad=lenA-lenB;
           }
           while (gad>0){
    
               left=left.next;
               gad--;
           }
           while (left!=null){
    
               if (left==right){
    
                   return left;
               }
               left=left.next;
               right=right.next;
           }
           return null;

    }
}