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

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

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    int length1=0, length2=0;
    struct ListNode* temp1=pHead1, * temp2=pHead2;
    // 统计长度
    while(temp1 || temp2){
        if(temp1){
            length1++;
            temp1 = temp1->next;
        }
        if(temp2){
            length2++;
            temp2 = temp2->next;
        }
    }

    int gap;
    if(length1>length2){
        gap = length1-length2;
        for(int i=0; i<gap; i++){
            pHead1=pHead1->next;
        }
        while(pHead1!=pHead2){
            pHead1=pHead1->next;
            pHead2=pHead2->next;
        }
        return pHead1;
    }else{
        gap = length2-length1;
        for(int i=0; i<gap; i++){
            pHead2=pHead2->next;
        }
        while(pHead1!=pHead2){
            pHead1=pHead1->next;
            pHead2=pHead2->next;
        }
        return pHead1;
    }
}

思路：先计算两个链表的长度，然后让较长链表的指针先移动长度差的步数，之后两个指针同步移动来找第一个公共节点