// 面试题23：链表中环的入口结点

// 题目：一个链表中包含环，如何找出环的入口结点？例如，在图3.8的链表中，

// 环的入口结点是结点3。

#include <iostream>

#include "List.h"

ListNode* MeetingNode(ListNode* pHead)//鲁棒一：先确定有没有环，有的话先求得环中任意一个节点

{

    if (pHead == nullptr)//若头结点为空

        return nullptr;

    ListNode* pSlow = pHead->m_pNext;

    if (pSlow == nullptr)//若只有一个节点

        return nullptr;

    ListNode* pFast = pSlow->m_pNext;

    while (pFast != nullptr && pSlow != nullptr)//判断碰到尾节点后有没有环

    {

        if (pFast == pSlow)

            return pFast;

        pSlow = pSlow->m_pNext;

        pFast = pFast->m_pNext;

        if (pFast != nullptr)//判断碰到尾节点后有没有环

            pFast = pFast->m_pNext;

    }

    return nullptr;

}

ListNode* EntryNodeOfLoop(ListNode* pHead)//开始计算入口节点，第一步先求环的个数，第二步通过两个前后指针计算入口节点

{

    ListNode* meetingNode = MeetingNode(pHead);

    if (meetingNode == nullptr)//如果存在环，得到一个环中节点

        return nullptr;

    // 得到环中结点的数目

    int nodesInLoop = ;

    ListNode* pNode1 = meetingNode;

    while (pNode1->m_pNext != meetingNode)

    {

        pNode1 = pNode1->m_pNext;

        ++nodesInLoop;

    }

    // 先移动pNode1，次数为环中结点的数目

    pNode1 = pHead;

    for (int i = ; i < nodesInLoop; ++i)

        pNode1 = pNode1->m_pNext;

    // 再移动pNode1和pNode2

    ListNode* pNode2 = pHead;

    while (pNode1 != pNode2)//二者只能相遇在入口处

    {

        pNode1 = pNode1->m_pNext;

        pNode2 = pNode2->m_pNext;

    }

    return pNode1;

}

// ==================== Test Code ====================

void Test(const char* testName, ListNode* pHead, ListNode* entryNode)

{

    if (testName != nullptr)

        printf("%s begins: ", testName);

    if (EntryNodeOfLoop(pHead) == entryNode)

        printf("Passed.\n");

    else

        printf("FAILED.\n");

}

// A list has a node, without a loop

void Test1()

{

    ListNode* pNode1 = CreateListNode();

    Test("Test1", pNode1, nullptr);

    DestroyList(pNode1);

}

// A list has a node, with a loop

void Test2()

{

    ListNode* pNode1 = CreateListNode();

    ConnectListNodes(pNode1, pNode1);

    Test("Test2", pNode1, pNode1);

    delete pNode1;

    pNode1 = nullptr;

}

// A list has multiple nodes, with a loop

void Test3()

{

    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);

    ConnectListNodes(pNode5, pNode3);

    Test("Test3", pNode1, pNode3);

    delete pNode1;

    pNode1 = nullptr;

    delete pNode2;

    pNode2 = nullptr;

    delete pNode3;

    pNode3 = nullptr;

    delete pNode4;

    pNode4 = nullptr;

    delete pNode5;

    pNode5 = nullptr;

}

// A list has multiple nodes, with a loop

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);

    ConnectListNodes(pNode5, pNode1);

    Test("Test4", pNode1, pNode1);

    delete pNode1;

    pNode1 = nullptr;

    delete pNode2;

    pNode2 = nullptr;

    delete pNode3;

    pNode3 = nullptr;

    delete pNode4;

    pNode4 = nullptr;

    delete pNode5;

    pNode5 = nullptr;

}

// A list has multiple nodes, with a loop

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);

    ConnectListNodes(pNode5, pNode5);

    Test("Test5", pNode1, pNode5);

    delete pNode1;

    pNode1 = nullptr;

    delete pNode2;

    pNode2 = nullptr;

    delete pNode3;

    pNode3 = nullptr;

    delete pNode4;

    pNode4 = nullptr;

    delete pNode5;

    pNode5 = nullptr;

}

// A list has multiple nodes, without a loop

void Test6()

{

    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("Test6", pNode1, nullptr);

    DestroyList(pNode1);

}

// Empty list

void Test7()

{

    Test("Test7", nullptr, nullptr);

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    Test7();

    system("pause");

    return ;

}