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

原题链接—acwing

1. 两个指针终会相遇，就算一个指针跑的快，他最后也会停下来，等待下一个指针赶上 ，所以如果有公共点，那么一定会相遇，即使第一遍扫描的时候错过去了那个公共的节点，最后从对方的链表再次扫描的时候，到达链表尾部的时候还是会扫描到那个节点，因为走的路径一样，肯定同时遍历完链表。这里其实不好想，自己画图走一遍试试就好了。
2. 两个指针走的总路线是一样的
3. 如果2个链表没有相同的部分，指针都会在链表的尾部的空指针处停下来，然后返回空

图示：总路程是一样的

 //两个指针终会相遇，就算一个指针跑的快，他最后也会停下来，等待下一个指针赶上
 //两个指针走的总路线是一样的
 //如果2个链表没有相同的部分，指针都会在链表的尾部的空指针处停下来，然后返回空
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p = headA,q = headB;
        while(p!=q){//两个指针一起开始走，把2个链表同时遍历一遍，走相同的路径
    //如果p为空了，那就转到headB开始走，如果链表非空，那就走到p的下一个节点
            p = p ? p->next:headB;
            q = q ? q->next:headA;//同理
        }
        return q;//找到的p和q就是相同部分的头结点
        
    }
};