《剑指offer》第五十二题（两个链表的第一个公共结点）

// 面试题52：两个链表的第一个公共结点
// 题目：输入两个链表，找出它们的第一个公共结点。#include <iostream>
#include "List.h"unsigned int GetListLength(ListNode* pHead);
//下面这个时间复杂度是O（m+n），且不用辅助空间
//另一种方法是使用两个栈，从尾到头比较，这样时间复杂度不变，空间复杂度O（m+n）
ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2)
{
    // 得到两个链表的长度
    unsigned int nLength1 = GetListLength(pHead1);
    unsigned int nLength2 = GetListLength(pHead2);
    int nLengthDif = nLength1 - nLength2;//先设链表1比链表2长，求长度差    ListNode* pListHeadLong = pHead1;
    ListNode* pListHeadShort = pHead2;
    if (nLength2 > nLength1)//万一链表2比链表1长，重设
    {
        pListHeadLong = pHead2;
        pListHeadShort = pHead1;
        nLengthDif = nLength2 - nLength1;
    }    // 先在长链表上走几步，再同时在两个链表上遍历
    for (int i = ; i < nLengthDif; ++i)
        pListHeadLong = pListHeadLong->m_pNext;    while ((pListHeadLong != nullptr) &&
        (pListHeadShort != nullptr) &&
        (pListHeadLong != pListHeadShort))//找到第一个相等的节点
    {
        pListHeadLong = pListHeadLong->m_pNext;
        pListHeadShort = pListHeadShort->m_pNext;
    }    // 得到第一个公共结点
    ListNode* pFisrtCommonNode = pListHeadLong;    return pFisrtCommonNode;
}unsigned int GetListLength(ListNode* pHead)//得到链表的长度
{
    unsigned int nLength = ;
    ListNode* pNode = pHead;
    while (pNode != nullptr)
    {
        ++nLength;
        pNode = pNode->m_pNext;
    }    return nLength;
}// ====================测试代码====================
void DestroyNode(ListNode* pNode);void Test(const char* testName, ListNode* pHead1, ListNode* pHead2, ListNode* pExpected)
{
    if (testName != nullptr)
        printf("%s begins: ", testName);    ListNode* pResult = FindFirstCommonNode(pHead1, pHead2);
    if (pResult == pExpected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}// 第一个公共结点在链表中间
// 1 - 2 - 3 \
//            6 - 7
//     4 - 5 /
void Test1()
{
    ListNode* pNode1 = CreateListNode();
    ListNode* pNode2 = CreateListNode();
    ListNode* pNode3 = CreateListNode();
    ListNode* pNode4 = CreateListNode();
    ListNode* pNode5 = CreateListNode();
    ListNode* pNode6 = CreateListNode();
    ListNode* pNode7 = CreateListNode();    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode6);
    ConnectListNodes(pNode4, pNode5);
    ConnectListNodes(pNode5, pNode6);
    ConnectListNodes(pNode6, pNode7);    Test("Test1", pNode1, pNode4, pNode6);    DestroyNode(pNode1);
    DestroyNode(pNode2);
    DestroyNode(pNode3);
    DestroyNode(pNode4);
    DestroyNode(pNode5);
    DestroyNode(pNode6);
    DestroyNode(pNode7);
}// 没有公共结点
// 1 - 2 - 3 - 4
//
// 5 - 6 - 7
void Test2()
{
    ListNode* pNode1 = CreateListNode();
    ListNode* pNode2 = CreateListNode();
    ListNode* pNode3 = CreateListNode();
    ListNode* pNode4 = CreateListNode();
    ListNode* pNode5 = CreateListNode();
    ListNode* pNode6 = CreateListNode();
    ListNode* pNode7 = CreateListNode();    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode5, pNode6);
    ConnectListNodes(pNode6, pNode7);    Test("Test2", pNode1, pNode5, nullptr);    DestroyList(pNode1);
    DestroyList(pNode5);
}// 公共结点是最后一个结点
// 1 - 2 - 3 - 4 \
//                7
//         5 - 6 /
void Test3()
{
    ListNode* pNode1 = CreateListNode();
    ListNode* pNode2 = CreateListNode();
    ListNode* pNode3 = CreateListNode();
    ListNode* pNode4 = CreateListNode();
    ListNode* pNode5 = CreateListNode();
    ListNode* pNode6 = CreateListNode();
    ListNode* pNode7 = CreateListNode();    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode7);
    ConnectListNodes(pNode5, pNode6);
    ConnectListNodes(pNode6, pNode7);    Test("Test3", pNode1, pNode5, pNode7);    DestroyNode(pNode1);
    DestroyNode(pNode2);
    DestroyNode(pNode3);
    DestroyNode(pNode4);
    DestroyNode(pNode5);
    DestroyNode(pNode6);
    DestroyNode(pNode7);
}// 公共结点是第一个结点
// 1 - 2 - 3 - 4 - 5
// 两个链表完全重合
void Test4()
{
    ListNode* pNode1 = CreateListNode();
    ListNode* pNode2 = CreateListNode();
    ListNode* pNode3 = CreateListNode();
    ListNode* pNode4 = CreateListNode();
    ListNode* pNode5 = CreateListNode();    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);    Test("Test4", pNode1, pNode1, pNode1);    DestroyList(pNode1);
}// 输入的两个链表有一个空链表
void Test5()
{
    ListNode* pNode1 = CreateListNode();
    ListNode* pNode2 = CreateListNode();
    ListNode* pNode3 = CreateListNode();
    ListNode* pNode4 = CreateListNode();
    ListNode* pNode5 = CreateListNode();    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);    Test("Test5", nullptr, pNode1, nullptr);    DestroyList(pNode1);
}// 输入的两个链表有一个空链表
void Test6()
{
    Test("Test6", nullptr, nullptr, nullptr);
}void DestroyNode(ListNode* pNode)
{
    delete pNode;
    pNode = nullptr;
}int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    system("pause");
    return ;
}