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

/**
 * 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
    struct ListNode* p1 = pHead1;
    struct ListNode* p2 = pHead2;

    if (pHead1 == NULL || pHead2 == NULL) {
        return NULL;
    }

    // 先遍历两条链表，算出各链表的长度,然后再根据两者长度的差值，先后开始遍历两个链表，两链表遍历的相遇点就是目标节点
    int LenP1 = 0;
    int LenP2 = 0;
    int m = 0;
    while (p1) {
        p1 = p1->next;
        LenP1++;
    }
    while (p2) {
        p2 = p2->next;
        LenP2++;
    }
    m = LenP1 - LenP2;
    if (m > 0) {
        while (pHead1) {
            if (pHead1 == pHead2) {
                return pHead1;
            }
            pHead1 = pHead1->next;
            if (m <= 0) {
                pHead2 = pHead2->next;
            }
            m--;
        }
    } else {
        while (pHead2) {
            if (pHead1 == pHead2) {
                return pHead2;
            }
            pHead2 = pHead2->next;
            if (m >= 0) {
                pHead1 = pHead1->next;
            }
            m++;
        }
    }
    return NULL;
}