Force buckle 160. intersecting linked list

Portal ： Intersecting list

Their thinking

Because the intersection of the two linked lists must be y shape , So the overlapped parts of the two intersecting linked lists must be of equal length , The length difference is in the disjoint part in front of the two linked lists , Therefore, we can judge the length difference between the two linked lists in advance , Let the long linked list take the steps of difference first , After that, double pointers can traverse at the same time to determine whether they coincide

Code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        int lenA=0;
        int lenB=0;
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        while(nodeA != null){
    
            lenA++;
            nodeA = nodeA.next;
        }
        while(nodeB != null){
    
            lenB++;
            nodeB = nodeB.next;
        }
        ListNode longer = headA;
        ListNode shorter = headB;
        int diff = lenA - lenB;
        if(lenA < lenB){
    
            longer = headB;
            shorter = headA;
            diff = lenB - lenA;
        }
        
        while(diff-- > 0){
    
            longer = longer.next;
        }
        while(longer != null && shorter != null){
    
            if(longer == shorter){
    
                return longer;
            }
            longer = longer.next;
            shorter = shorter.next;
        }
        return null;
    }
}

• Time complexity O(m+n)
• Spatial complexity O(1)