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

1. 链表长度差
   思路：先统计两个链表的长度，计算他们的差值，然后将两个链表对齐，再去寻找公共节点即可。

*2 双指针

• 思想：使用两个指针pFirstNode和pSecondNode分别指向两个链表pHead1，pHead2的头结点，然后同时分别逐结点遍历，

• 当pFirstNode到达链表pHead1的末尾时，重新定位到链表headB的头结点；当pSecondNode到达链表headB的末尾时，

• 重新定位到链表pHead1的头结点。这样，当pFirstNode和pSecondNode相遇时，所指向的结点就是第一个公共结点。

• 简言之，链表拼接，然后双指针遍历查找

• 3 栈 (计算不全 5/8)

• 思想：将节点放入栈，根据栈的先进后出原理，栈弹出节点，若弹出节点不相等，则退出，且计算弹出节点的个数commLen，

• 根据链表1的个数pHeadLen1 减去 commLen 等于 链表1移动的个数pHeadMoveLen, 计算公共节点

/*
* 1. 链表长度差
* 思路：先统计两个链表的长度，计算他们的差值，然后将两个链表对齐，再去寻找公共节点即可。
*/

ListNode* ListsLenDiffClass::FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
    if (pHead1 == nullptr || pHead2 == nullptr) {
        return nullptr;
    }
    CreateListClass createListClass;
    int pHeadLen1 = 0;
    int pHeadLen2 = 0;
    ListNode* pFirstNode = pHead1;
    ListNode* pSecondNode = pHead2;
    while (pFirstNode != nullptr) {
        pHeadLen1++;
        pFirstNode = pFirstNode->next;
    }

    while (pSecondNode != nullptr) {
        pHeadLen2++;
        pSecondNode = pSecondNode->next;
    }

    if (pHeadLen1 < pHeadLen2) {
        int pHeadLen = pHeadLen2 - pHeadLen1;
        while(pHeadLen--) {
            pHead2 = pHead2->next;
        }
    } else {
        int pHeadLen = pHeadLen1 - pHeadLen2;
        while(pHeadLen--) {
            pHead1 = pHead1->next;
        }
    }

    while(pHead1 != nullptr && pHead2 != nullptr) {
        if (pHead1 == pHead2) {
            return pHead1;
        }
        pHead1 = pHead1->next;
        pHead2 = pHead2->next;
    }

    return nullptr;
}

/*
*2 双指针
* 思想：使用两个指针pFirstNode和pSecondNode分别指向两个链表pHead1，pHead2的头结点，然后同时分别逐结点遍历，
* 当pFirstNode到达链表pHead1的末尾时，重新定位到链表headB的头结点；当pSecondNode到达链表headB的末尾时，
* 重新定位到链表pHead1的头结点。这样，当pFirstNode和pSecondNode相遇时，所指向的结点就是第一个公共结点。
* 简言之，链表拼接，然后双指针遍历查找
*/

ListNode* TwoPointersClass::FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
    if (pHead1 == nullptr || pHead2 == nullptr) {
        return nullptr;
    }
    ListNode* pFirstNode = pHead1;
    ListNode* pSecondNode = pHead2;

    while(pFirstNode != pSecondNode) {
        if (pFirstNode == nullptr) {
            pFirstNode = pHead2;
        } else {
            pFirstNode = pFirstNode->next;
        }

        if (pSecondNode == nullptr) {
            pSecondNode = pHead1;
        } else {
            pSecondNode = pSecondNode->next;
        }
    }
    return pFirstNode;
}


/*
* 3 栈 
* 思想：将节点放入栈，根据栈的先进后出原理，栈弹出节点，若弹出节点不相等，则退出，且计算弹出节点的个数commLen，
*     根据链表1的个数pHeadLen1 减去 commLen 等于 链表1移动的个数pHeadMoveLen, 计算公共节点
*/

ListNode* StackClass::FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
    if (pHead1 == nullptr || pHead2 == nullptr) {
        return nullptr;
    }
    ListNode* pFirstNode = pHead1;
    ListNode* pSecondNode = pHead2;
    std::stack<ListNode*> listNodeStack1;
    std::stack<ListNode*> listNodeStack2;
    while (pFirstNode != nullptr) {
        listNodeStack1.push(pFirstNode);
        pFirstNode = pFirstNode->next;
    }
    while (pSecondNode != nullptr) {
        listNodeStack2.push(pSecondNode);
        pSecondNode = pSecondNode->next;
    }

    int listNodeStackSize1 = listNodeStack1.size();
    int pHeadMoveLen1 = 0;
    //计算公共节点
    while(!listNodeStack1.empty() && !listNodeStack2.empty()) {
        if (listNodeStack1.top() != listNodeStack2.top()) {
            break;
        } else {
            listNodeStack1.pop();
            listNodeStack2.pop();
            pHeadMoveLen1++;
        }
    }

    int pHeadMoveLen2 = listNodeStackSize1 - pHeadMoveLen1;
    while(pHeadMoveLen2--) {
        pHead1 = pHead1->next;
    }

    return pHead1;
}