【剑指offer】两个链表的第一个公共结点

主要分析了链表尾部有环的时候怎么处理，无环的解法参考selfboot。

两个无环的链表

当链表无环时，分为有交点和无交点，而每种情况下又分为等长和不等长。当链表等长时，同时从头遍历两个链表，最晚在第一次遍历完成时就能判断并返回交点；当其不等长时，某链表遍历完成，使其指向另一个链表的头结点，在第二次遍历时就能找出相同的结点或者返回NULL。

ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
    if (pHead1 == NULL || pHead2 == NULL) return NULL;
    ListNode* p1 = pHead1;
    ListNode* p2 = pHead2;
    while (p1 != p2){
        p1 = (p1 == NULL ? pHead2 : p1->next);
        p2 = (p2 == NULL ? pHead1 : p2->next);
    }
    return p1;
}

两个尾部有环的链表

需要先检索两个链表的环入口结点，即loop点。
①如果loop点相同：解法同无环的解法，只不过拼接点改为了loop点。

②如果loop点不同：当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。

ListNode* bothLoop(ListNode* pHead1, ListNode* loop1, ListNode* pHead2, ListNode* loop2){
    ListNode* p1 = NULL;
    ListNode* p2 = NULL;
    if (loop1 == loop2){
        while (p1 != p2){
            p1 = (p1 == loop1 ? pHead2 : p1->next); //解法同无环解法，拼接点设置为loop点即可。
            p2 = (p2 == loop1 ? pHead1 : p2->next);
        }
        return p1;
    }
    else {
        p1 = loop1->next; //当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。
        while (p1 != loop1){
            if (p1 == loop2){
                return loop1;
            }
            p1 = p1->next;
        }
        return NULL;
    }
}

附上完整代码

class Solution{
    public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (pHead == NULL || pHead->next == NULL)
            return NULL;
        ListNode* p1 = pHead->next; //慢指针，一次前进一格
        ListNode* p2 = pHead->next->next; //快指针，一次前进两格
        while (p1 != p2)
        {
            if (p2 == NULL || p2->next == NULL) //如果快指针p2走到头了，说明链表不成环
            {
                return NULL;
            }
            p1 = p1->next; //快慢前进
            p2 = p2->next->next;
        } //假如成环，会在p1、p2相遇时结束第一个while。此时p1到入口的距离等于head到入口的距离
        p2 = pHead; //让p2指向链表头部，p1位置不变。
        while (p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1; //p1, p2每次走一步直到p1 == p2; 此时p1指向环的入口。
    }

ListNode* bothLoop(ListNode* pHead1, ListNode* loop1, ListNode* pHead2, ListNode* loop2){
    ListNode* p1 = NULL;
    ListNode* p2 = NULL;
    if (loop1 == loop2){
        while (p1 != p2){
            p1 = (p1 == loop1 ? pHead2 : p1->next);        //解法同无环解法，拼接点设置为loop点即可。
            p2 = (p2 == loop1 ? pHead1 : p2->next);
        }
        return p1;
    }
    else {
        p1 = loop1->next;                                  //当p1点从loop出发，第一次回到loop1前，若相遇loop2，则相交，否则无交点。
        while (p1 != loop1){
            if (p1 == loop2){
                return loop1;
            }
            p1 = p1->next;
        }
        return NULL;
    }
}
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2){
    if (pHead1 == NULL || pHead2 == NULL) return NULL;
    ListNode* p1 = pHead1;
    ListNode* p2 = pHead2;
    ListNode* loop1 = EntryNodeOfLoop(pHead1);            //查询是否有环的入口结点，并返回
    ListNode* loop2 = EntryNodeOfLoop(pHead2);
    if (loop1 == NULL && loop2 == NULL){                  //链表都无环解法，最坏时间复杂度O(m + n)
        while (p1 != p2){
            p1 = (p1 == NULL ? pHead2 : p1->next);
            p2 = (p2 == NULL ? pHead1 : p2->next);
        }
        return p1;
    }
    else if (loop1 != NULL && loop2 != NULL){             //链表都有环
        return bothLoop(pHead1,loop1,pHead2,loop2);
    }
    else{                                                 //一个有环一个无环，无交点
        return NULL;
    }
}
};