题解 | #两个链表的第一个公共结点#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
int length(struct ListNode *Head){
    int n=0;
    struct ListNode *p=Head;
    while(p){
        p=p->next;
        n++;
    }
    return n;
} 
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if(pHead1==NULL||pHead2==NULL){
        return NULL;
    }
    int n1=length(pHead1),n2=length(pHead2);
    int sub=0;
    if(n1>=n2){
        sub=n1-n2;
        for(int i=0;i<sub;i++){
            pHead1=pHead1->next;
        }
        while(pHead1&&pHead2&&(pHead1!=pHead2)){
            pHead1=pHead1->next;
            pHead2=pHead2->next;
        }
    }
    else{
        sub=n2-n1;
        for(int i=0;i<sub;i++){
            pHead2=pHead2->next;
        }
        while(pHead1&&pHead2&&(pHead1!=pHead2)){
            pHead1=pHead1->next;
            pHead2=pHead2->next;
        }
    }
    return pHead1;
}

要找两个链表可能的公共结点，首先判断第一个链表或者第二个链表是否为空，是的话则返回空。

这两个均是单链表故不循环，因此不能用快慢指针来判断。求出两个链表长度的差值目的是寻找可能的两个指针都指向同一个结点的情况。

你说会不会出现第一个结点就是公共部分呢？有可能但这样的话两个链表的差值就是0了。

如图所示这是两种情况，第一个链表的长度是5，第二个链表的长度是5，两个链表的差值是1，从第二个链表的视角看分别是第三个和第四个结点时才出现的公共部分，正是因为我们不能确定第几个结点出现时所以才要依次循环去找到可能出现的地方。

确定两个指针循环的次数一致后便依次指向下一个结点除非碰到第一个链表循环完毕或者第二个链表循环完毕或者指向相同的结点时才会停止。

返回第一个或第二个链表的剩余部门即为公共部分。