[leetcode refers to offer 52. The first common node of two linked lists (simple)]

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 .

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 , therefore 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 .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The problem solving process ：

source LeetCode user ： gem
Set intersection list length c, Linked list 1 Except that the length of the intersection is a, Linked list 2 Except that the length of the intersection is b, Yes

a + c + b = b + c + a
If there is no intersection , be a + b = b + a

/** * 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) {
    
        if(headA==null || headB==null)
            return null;
        ListNode n1 = headA, n2 = headB;
        while(n1!=n2){
    
            n1 = n1==null ? headB:n1.next;
            n2 = n2==null ? headA:n2.next;
        }
        return n1;
    }
}

Execution results ：