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

C语言

1、先计算得到两个链表的长度，得到两链表的差值

2、将长链表根据长度差值，长链表向后移动直到长链表与短链表一样长度

3、循环判断两链表当前节点地址是否相等，不相等就一起移到下一节点

struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {

    int list1Count = 0, list2Count = 0;

    struct ListNode *tmp, *longList, *shortList;    //声明长短链表指针

    tmp = pHead1;           //得到pHead1的长度

    while(tmp){

        list1Count++;

        tmp = tmp->next;

    }

    tmp = pHead2;           //得到pHead2的长度

    while(tmp){

        list2Count++;

        tmp = tmp->next;

    }

    if(list1Count >= list2Count){   //将pHead1 pHead2放入对应的长短链表里面

        longList = pHead1, shortList = pHead2;

    }else{

        longList = pHead2, shortList = pHead1;

    }

    //由公共部分是一样的，可以看作右对齐，此时将长链表的移动到和短链表一样长

    for(int i=0; i<abs(list1Count-list2Count); i++){

        longList = longList->next;

    }

    //由于公共部分节点的地址是一样的，直接判断长短链表当前节点的地址是否一致即可

    while(longList && shortList){

        if(longList == shortList){

            return longList;

        }

        longList = longList->next;

        shortList = shortList->next;

    }

    return NULL;

}