题解 | NO.10#两个链表的第一个公共结点#2.29

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

/**
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1,
                                     struct ListNode* pHead2 ) {
    int i = 1, j = 1, k = 0;   //i，j分别记录两个链表的长度
    struct ListNode* p = pHead1, *q = pHead2;   //用p，q分别遍历两个链表
    while (p != NULL) {
        ++i;
        p = p->next;
    }
    while (q != NULL) {
        ++j;
        q = q->next;
    }
    p = pHead1;   //将p，q分别重新指向两个链表的头结点
    q = pHead2;
    if (i <= j) {   //链表1长度小于等于链表2
        k = j - i;
        for (int s = 1; s <= k; ++s) {   //调整q的位置，使p与q所指结点后的链表长度相等
            q = q->next;
        }
    } else {    //链表2长度小于等于链表1
        k = i - j;
        for(int s = 1; s <=k; ++s){    //调整p的位置，使p与q所指结点后的链表长度相等
            p = p->next;
        }
    }
    while (p != q && p != NULL) {    //找到链表第一个公共结点停止，或者链表没有公共结点
        p = p->next;
        q = q->next;
    }
    return p;   //返回第一个公共结点，或者返回空链表
}