题目描述

66.两个链表的第一个公共结点

方法1

用两个指针分别指向两个链表headA、headB的头结点，向后遍历。
当指针遍历到链表末尾时，定位到另一个链表的表头。
当两个指针相遇时，所指向的结点就是公共结点，两个指针遍历的元素数量相同。如果没有公共结点，两个指针都会指向空nullptr。

遍历的图解可以看这个用户写的题解：
https://www.acwing.com/solution/content/26708/

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p1=headA,p2=headB;
        while(p1!=p2){
            if(p1!=NULL)//p1没有走到结尾
                p1=p1->next;
            else
                p1=headB;//p1指向另一个链表表头
            if(p2!=NULL)
                p2=p2->next;
            else
                p2=headA;
        }
        return p1;
    }
};