leetcode刷题日记:160. Intersection of Two Linked Lists（相交链表）

给出两个单链表的头结点headA与headB，让我们找出两个链表相接的起始节点，如果两个链表不存在相交结点返回null。
我们就先假设存在这样两个链表，链表1与链表2，假设链表1的长度为 $L_1$ 和 $L_2$ ,假设对于两个链表，从相交的结点向后数长度为 $L_{1,2}$ ,则在相交结点之前链表1的长度未 $L_1-L_{1, 2}$ 链表2的长度为 $L_2- L_{1, 2}$ ,对于两条链表无相交的情况 $L_{1,2}=0$ ,如图是具有相交部分的两个链表的图示：
在这里插入图片描述
不相交的两个链表的图示你可以想象出来，将后面的那一部分去掉就行了。
我们现在想的就是如何让遍历链表1的指针与遍历链表2的指针能够相遇在同一节点，如图所示：

显然这两个链表在相交部分前面的部分可能不一样长也就是 $L_1\neq L_2$ ,也就是我们我们直接从头结点遍历遍历到尾结点是不行的，我们们来看一下遍历到尾节点之后链表1走了多远 $L_1-L_{1,2})+L_{1,2}$ 链表2走过的长度为 $L_2-L_{1,2})+L_{1,2}$ 是不是我们可以看出有一段是公共的长度，它们两个走过的长度不一样就不一样在 $L_1-L_{1,2})$ 与 $L_2-L_{1,2})$ 这两项上，如果说在链表1走过的路程加上一个 $L_2-L_{1,2})$ ,在链表2走过的路程加上一个 $L_1-L_{1,2})$ ，它们是不是就一样了，都为 $L_1-L_{1,2})+L_{1,2}+(L_2-L_{1,2})$
我们整理一下：
链表1走过的路程为： ${(L_1-L_{1,2})+L_{1,2}\}+(L_2-L_{1,2})$
链表2走过的路程为： $L_1-L_{1,2})+\{(L_{1,2})+(L_2-L_{1,2})\}$
在这两个式子中，我们发现{}所围的为自己链表的长度，其余的为对方链表的在相交之前的部分的长度。也就是说如果我们遍历自身链表，到结尾之后再去遍历对方链表就能让两个指针同步。
两个指针同步之后，如果在同步之后后面仍有结点，则说明有相交部分，如果同步之后后面没有结点了，则说明这两个链表之间没有相交部分。
有了上面的思路，我们可以写出下面的代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *p=headA, *q=headB;
    while(p!=q){
        if(p==NULL){
            p = headB;
        }else{
            p = p->next;
        }
        if(q==NULL){
            q = headA;
        }else{
            q = q->next;
        }
    }
    return p;
}