Linked list - the first common node of two linked lists

subject ：

Enter two acyclic one-way linked lists , Find their first common node , If there is no public node, null is returned .（ Note that because the incoming data is a linked list , So the error test data prompt is displayed in other ways , Make sure the incoming data is correct ）
for example , Input {1,2,3},{4,5},{6,7} when , The structure of two acyclic one-way linked lists is shown in the figure below ：

You can see that the node value of their first common node is 6, Therefore, the returned node value is 6 The node of .
Input description ：
Input is divided into yes 3 paragraph , The first paragraph is the non-public part of the first linked list , The second paragraph is the non-public part of the second linked list , The third paragraph is the common part of the first linked list and the second linked list . The backstage will 3 Two parameters are assembled into two linked lists , And the corresponding head nodes of the two linked lists are passed into the function FindFirstCommonNode Inside , The only input the user gets is pHead1 and pHead2.
Return value description ：
Return the incoming pH*=ead1 and pHead2 First common node of , The linked list with this node as the head node will be printed in the background .

Their thinking ：

Because we are looking for the first common node of the two linked lists , So our first thought may be to traverse the linked list , Find the first public node , But this method has two cycles , The time complexity will be high , We hope to find a method of linear time complexity to solve the problem .
If you want to solve the problem with linear time complexity , There is an ideal state ： The length of the two linked lists is the same .

In this case , We can separately from the linked list a And the list b The head node of starts traversing , Until the first common node appears , Return the node , Otherwise, there is no public node , At this time, the pointer just goes to the end of the linked list , Pointer to nullptr, return nullptr.
however , The length of the input list of topics is not the same , So we try to construct them into an ideal state , Suppose the linked list a The length is m, Linked list b The length is n,m！=n, however m+n=n+m, So we can link the linked lists with each other .

Whether the link is in front or behind , Because the length is the same , From the end of the linked list , Will be the end of two original lists ,

• If there are public nodes , Then from the tail, it corresponds one by one , We just need to traverse from front to back , Just find the first public node .
• If there is no public node , Then there is no one-to-one corresponding node from the tail , Traverse from front to back until the end , return nullptr that will do .

Solution code ：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1=pHead1,*p2=pHead2;
        // Until we finally find the common node or reach the tail of the synthetic linked list 
        while(p1!=p2){
            p1=p1?p1->next:pHead2;// If p1 Traverse to the tail , From the linked list 2 Start and then traverse 
            p2=p2?p2->next:pHead1;// If p2 Traverse to the tail , From the linked list 1 Start and then traverse 
        }
        return p1;
    }
};