Linked list intersection (linked list)

subject ：

Given two （ A one-way ） Linked list , Determine whether they intersect and return to the intersection point . Note that the definition of intersection is based on the node reference , Not based on the value of the node . let me put it another way , If the second part of a linked list k A node and the second... Of another linked list j Two nodes are the same node （ References are exactly the same ）, Then the two linked lists intersect .

Ideas ： Align the tail of the linked list , Look for the same part from a certain position to the tail

public class Lianbiaoxiangjiao {
    public ListNode getIntersectionNode(ListNode headA,ListNode headB){
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0,lenB = 0;
        while (curA != null){
            // Find the linked list A The length of 
            lenA++;
            curA = curA.next;
        }
        while (curB !=null){
            // Find the linked list B The length of 
            lenB++;
            curB = curB.next;
        }
        // Restore A,B Object pointer 
        curA = headA;
        curB = headB;

        // Give Way curA For the head of the longest linked list ,lenA Is its length 
        if (lenB > lenA){
            int temp = lenA;
            lenA = lenB;
            lenB = temp;

            ListNode tempNode = curA;
            curA = curB;
            curB = tempNode;
        }

        // Length difference 
        int gap = lenA - lenB;
        // Give Way curA and curB Last position alignment 
        while (gap>0){
            curA = curA.next;
            gap--;
        }
        // Traverse curA and curB, If you encounter the same, you will directly return 
        while (curA !=null){
            if (curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        // If not found, return null 
        return null;
    }
}