//找到链表中环的入口节点 //如果环有n个节点，那么指针p1先向前走n步，然后p1,p2一起往前走，直到相遇,相遇的节点就是入口节点
//接下来求环的节点个数：用快慢指针，如果相遇，必存在环，然后记下这个位置，再向前一边移动一边计数，当再次回到这个节点，就求出这个huan的个数

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//构建链表，显示链表
struct ListNode
{
    int       m_nValue;
    ListNode* m_pNext;
};

ListNode* CreateListNode(int value);
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext);
void PrintListNode(ListNode* pNode);
void PrintList(ListNode* pHead);
void DestroyList(ListNode* pHead);
void AddToTail(ListNode** pHead, int value);

ListNode* CreateListNode(int value)
{
    ListNode* pNode = new ListNode();
    pNode->m_nValue = value;
    pNode->m_pNext = NULL;

    return pNode;
}

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
{
    if(pCurrent == NULL)
    {
        printf("Error to connect two nodes.\n");
        exit(1);
    }

    pCurrent->m_pNext = pNext;
}

void PrintListNode(ListNode* pNode)
{
    if(pNode == NULL)
    {
        printf("The node is NULL\n");
    }
    else
    {
        printf("The key in node is %d.\n", pNode->m_nValue);
    }
}

void PrintList(ListNode* pHead)
{
    printf("PrintList starts.\n");

    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        printf("%d\t", pNode->m_nValue);
        pNode = pNode->m_pNext;
    }

    printf("\nPrintList ends.\n");
}

void DestroyList(ListNode* pHead)
{
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        pHead = pHead->m_pNext;
        delete pNode;
        pNode = pHead;
    }
}

void AddToTail(ListNode** pHead, int value)
{
    ListNode* pNew = new ListNode();
    pNew->m_nValue = value;
    pNew->m_pNext = NULL;

    if(*pHead == NULL)
    {
        *pHead = pNew;
    }
    else
    {
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != NULL)
            pNode = pNode->m_pNext;

        pNode->m_pNext = pNew;
    }
}
//找到快慢指针相遇的节点
ListNode* MeetingNode(ListNode* pHead){
    if(pHead==NULL)
        return NULL;
    ListNode* pSlow=pHead->m_pNext;
    if(pSlow==NULL)//就那一个节点，没有环
        return NULL;

    ListNode* pFast=pSlow->m_pNext;//
    while(pFast!=NULL && pSlow!=NULL)
    {
        if(pFast==pSlow)
            return pFast;

        pSlow=pSlow->m_pNext;//一次一步
        pFast=pFast->m_pNext;
        if(pFast!=NULL)
            pFast=pFast->m_pNext;//一次两步
    }
    return  NULL;//不存在环
}

int number(ListNode* pHead){
     ListNode* meetingNode=MeetingNode(pHead);
    if(meetingNode==NULL)
        return NULL;

    //得到环的节点数目
    int nodeOfLoop=1;
    ListNode* pNode1=meetingNode;//环中的一个节点
    while(pNode1->m_pNext!=meetingNode){
        pNode1=pNode1->m_pNext;
        ++nodeOfLoop;
    }
    return nodeOfLoop;

}
ListNode* EntryNodeOfLoop(ListNode* pHead){
    int nodeOfLoop=number(pHead);

    //找环的入口
    ListNode* pNode1=pHead;
    for(int i=0;i<nodeOfLoop;i++){
        pNode1=pNode1->m_pNext;//先走环的长度
    }

    //一起移动两个指针
    ListNode* pNode2=pHead;
    while(pNode1!=pNode2){
        pNode1=pNode1->m_pNext;
        pNode2=pNode2->m_pNext;
    }
    return pNode1;
}
int main()
{
    //构建有环的链表
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);
    ListNode* pNode6 = CreateListNode(6);

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
    ConnectListNodes(pNode5, pNode6);
    ConnectListNodes(pNode6, pNode3);

    ListNode* first=EntryNodeOfLoop(pNode1);
    cout<<first->m_nValue;

    return 0;
}