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

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

/**
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1,
                                     struct ListNode* pHead2 ) {

    //思路
    //分别遍历两个链表，获得长度A和B，假设A比B大
    //则对齐起点，A从第A-B个结点开始，B从头结点开始，两者开始向后遍历，二者相等时代表是第一个公共节点
    int list1Size = 0;
    int list2Size = 0;
    struct ListNode* p1 = pHead1;
    struct ListNode* p2 = pHead2;

    if ((pHead1 == NULL) || (pHead2 == NULL)) {
        return NULL;
    }
    //分别遍历两个链表
    while (p1 != NULL) {
        p1 = p1->next;
        list1Size++;
    }
    while (p2 != NULL) {
        p2 = p2->next;
        list2Size++;
    }

    //对齐起点
    if (list1Size > list2Size) {
        p1 = pHead1;
        p2 = pHead2;
        for (size_t i = 0; i < list1Size - list2Size; i++) {
            p1 = p1->next;
        }
    } else {
        p1 = pHead1;
        p2 = pHead2;
        for (size_t i = 0; i < list2Size - list1Size; i++) {
            p2 = p2->next;
        }
    }

    //二者相等时代表是第一个公共节点
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }

    return p1;
}