[leetcode] sword finger offer 52 The first common node of two linked lists

Enter two linked lists , Find their first common node .

For example, the following two linked lists are 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 .

Example 2：

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

Example 3：

Input ：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output ：null
Enter an explanation ： Starting from the respective heads , Linked list A by [2,6,4], Linked list B by [1,5]. Because these two linked lists don't intersect , the > With intersectVal It has to be for 0, and skipA and skipB It could be any value .
explain ： The two lists don't intersect , Therefore return null.

Be careful ：

If there is no intersection between two linked lists , return null.
After returning the result , The two lists still have to keep their original structure .
It can be assumed that there is no cycle in the whole linked list structure .
The procedure is as satisfying as possible O(n) Time complexity , And only O(1) Memory .

Answer key ：

    /** *  The finger of the sword  Offer 52.  The first common node of two linked lists  */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        /* *  set up  headA  The number of nodes is  a,headB  The number of nodes is  b, The number of common nodes of the two linked lists is  c, The public node is  node * headA  To  node  Former co owner  a-c  Nodes ,headB  To  node  Former co owner  b−c  Nodes , Two hands  A  and  B  Point to respectively  headA  and  headB * A  End of traversal  headA  Continue traversal after  headB,B  End of traversal  headB  Continue traversal after  headA *  When  A  and  B  When we met , here  A  The number of steps taken is  a+(b-c),B  The number of steps taken is  b+(a-c) * *  I walked through my world , Go through your world again  *  You walk through your world , Go through my world again  *  Eventually we will meet , Maybe on the way （ Public nodes ）, Maybe at the end （null） */
        ListNode A = headA;
        ListNode B = headB;

        while (A != B) {
    
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof