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

1. 常规输入检查
2. 检查 2 个链表是否有共同的 tail, 若无 则不存在公共节点，直接返回 NULL；若tail 相同，则说明有公共节点，继续以下步骤
3. 上述找 tail 过程，顺便记录 2 条 链表的长度，分别记为 x + z 和 y + z。 其中 x 代表 链表 1 除去 公共部分的 长度，y 代表 链表 2 除去 公共部分的 长度， z 代表 公共部分长度。
4. 将 较短的一条链表（假设是链表 1）反转，则此时 链表 2 的长度为 x + y。(反转后 链表1的 新 head 即原先的 tail)
5. 计算出 x, y, z
6. 从 反转后的链表的 新 head 处（原 tail）, 进行确定长度 z 的链表反转
7. 再次反转后的 新 head 即为 两个链表的公共节点。

// declares
struct ListNode* ReverseList(struct ListNode* pHead );
int ListLen(struct ListNode* pHead );
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // 常规输入检查
    if (!pHead1 || !pHead2 || (!pHead1->next && !pHead2->next)){
        return NULL;
    }
    
    // 检查 2 个链表是否有共同的 tail
    struct ListNode* pTail1 = pHead1;
    struct ListNode* pTail2 = pHead2;
    int count1 = 1;
    int count2 = 1;
    while(pTail1->next){
        count1++;
        pTail1 = pTail1->next;
        if(count1 > 1000){ return NULL; }
    }
    while(pTail2->next){
        count2++;
        pTail2 = pTail2->next;
        if(count2 > 1000){ return NULL; }
    }
    //  若不等 则不存在公共节点，直接返回 NULL
    if (pTail1 != pTail2){
        return NULL;
    }

    int x_z = count1;
    int y_z = count2;
    // 如果 链表1 长，则将两者调换一下
    if (x_z > y_z){
        x_z ^= y_z;
        y_z ^= x_z;
        x_z ^= y_z;

        struct ListNode* temp = pHead1;
        pHead1 = pHead2;
        pHead2 = temp;
    }
    // 翻转 短链表
    struct ListNode*  tail = ReverseList(pHead1);
    int x_y = ListLen(pHead2);
    // 计算 x,y,z
    int x = (x_z + x_y - y_z) >> 1;
    int y = x_y - x;
    int z = x_z - x;
    // 再次翻转给定长度 z
    struct ListNode* pFore = tail;
    struct ListNode* p = tail->next;
    tail->next = NULL;
    for(int i = 1; i < z; i++){
        struct ListNode*  pn = p->next;
        p->next = pFore;
        pFore = p;
        p = pn;
    }
    // 大功告成
    return pFore;
    
}

// 计数
int ListLen(struct ListNode* pHead ){
    int count = 0;
    while(pHead){
        count++;
        pHead = pHead->next;
        if(count > 2000){ return 0; }
    }
    return count;
}

// 翻转
struct ListNode* ReverseList(struct ListNode* pHead ) {
    if (!pHead || !pHead->next){
        return pHead;
    }
    struct ListNode* pFore = pHead;
    struct ListNode* p = pHead->next;
    pHead->next = NULL;
    while(p){
        struct ListNode* pn = p->next;
        p ->next = pFore;
        pFore = p;
        p = pn;
    }
    
    return pFore;
}