[数据结构与算法]剑指 Offer 52. 两个链表的第一个公共节点

题目：

输入两个链表，找出它们的第一个公共节点。

对于第一个样例 A和B的第一个公共节点是c1这里澄清以下什么叫公共节点并不是所谓的值相同就行了而是后面的节点都相同。
第二个样例一样

• 请大家仔细想一下这个怎么才能做到时间O(n) 空间O(1)的做法？先不要看下边的题解，没有思考这道题的印象就不会深！！！！

• 相信大家看到这里肯定经过了仔细思考了？不知道大家做出来没有

• 我刚开始的没想到我也想了倒着来遍历发觉不可行就放弃了看题解了不得不说刚开始没有想到一看leetcode那个官方题解不够仔细后来自己花了个图就非常明白了， 在这我也把图画出

• 在这如果两个链表 a与b不相交的部分长为 m b与a不相交的部分为n

• 如果m = n 这个情况好处理就是遍历 两个指针同时遍历

• 假设 m < n 这种情况看图

• 

• 这张图就表现出他们的结果了如果我们a遍历完紧接着遍历b 当然是两个一起遍历不能分开

• 他们的如果有相同部分一定会遍历道

• m > n也一样 (当然如果没看懂下面又官方题解)

• 代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
         ListNode*pa = headA;
         ListNode*pb = headB;

         while (pa != pb){   //如果 pa遍历到null 重新遍历 pa = pb不就是上图么
             pa = pa == NULL ? headB : pa -> next;
             pb = pb == NULL ? headA : pb -> next;
         }        

         return pa;
    }

• 官方题解