题解 | #链表中环的入口结点#

闭环的入口方法一
1. 判断链表是否有环
思想：可以设置快慢指针，快指针一次走两步，慢指针一次走一步，如果快指针追上了走的慢的指针，那么链表有环；
如果走到了链表尾部都没有追上，说明链表无环；
1. 如果有环，返回入口节点
思想：返回的节点一定在环内，如果计算出环中节点的个数count,快指针比慢指针多走count步，那么两个指针相遇时，
就是环的入口节点。
步骤：
第一步：慢指针走一步，快指针走两步，计算单链是否有环？
第二步：如果没有环，则输出为空；如果有环，则计算环的个数n；
第三步：前指针向后移动n位, 再查找前指针与后指针是否相等，若相等，则位入口节点，反之。

闭环的入口方法二
a、第一步，找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，
直到fast==slow找到在环中的相汇点。
b、第二步，找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,
设环中有n个节点，fast比slow多走r圈有2x=rn+x; x=rn;（r为圈数，n为一圈的结点数）
可以看出slow实际走了多个环的步数，再让fast指向链表头部，slow位置不变。
假设链表开头到环接口的距离是y，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，
那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = rn，即此时slow指向环的入口。

closedLoopList.h
```
#include <iostream>
```

struct ListNode {
int data;
struct ListNode * next;
ListNode(int x) : data(x), next(nullptr) {}
};

//基类链表
class BaseList {
public:
virtual ~BaseList() = default;
virtual ListNode *CreateClosedList() = 0;
virtual ListNode *ClosedLoopList(ListNode *pHead) = 0;
virtual int counterClosedLoopList(ListNode *pHead) = 0;
virtual void ShowClosedLoopList(ListNode *pHead) const = 0;

};

//实现基类的链表
class CompleteList : public BaseList {
public:
virtual ~CompleteList() = default;
ListNode *CreateClosedList() override;
ListNode *ClosedLoopList(ListNode *pHead) override;
int counterClosedLoopList(ListNode *pHead) override;
void ShowClosedLoopList(ListNode *pHead) const override;
};

class BaseClosedLoopList {
public:
virtual ~BaseClosedLoopList() = default;
virtual ListNode *EntryClosedLoopList(ListNode *pHead) = 0;

};

class CompleteClosedLoopListFirst : public BaseClosedLoopList {
public:
virtual ~CompleteClosedLoopListFirst() = default;
ListNode *EntryClosedLoopList(ListNode *pHead) override;
};

class CompleteClosedLoopListSecond : public BaseClosedLoopList {
public:
virtual ~CompleteClosedLoopListSecond() = default;
ListNode *EntryClosedLoopList(ListNode *pHead) override;
};

// 反转链表的模板
template <typename listtemplate="">
class CompleteClosedLoopListTemp {
public:
~CompleteClosedLoopListTemp() {}
ListNode *EntryClosedLoopList(ListNode *pHead) {
listTemplate.EntryClosedLoopList(pHead);
}
private:
ListTemplate listTemplate;
};</typename>

* closedLoopList.cpp

```c++
#include "closedLoopList.h"
#include <vector>

// 尾结点插入法创建链表
ListNode * CompleteList::CreateClosedList()
{
    int num = 1;
    //unique_ptr<ListNode> pHead = make_unique<ListNode> (num);
    ListNode *pHead = new ListNode(num);
    ListNode *p = pHead;

    //尾结点插入法
    for(int i = 2; i < 10; i++) {
        ListNode *q = new ListNode(i);
        p->next = q; //p节点插入listNode节点
        p = p->next; // 向后移位
    }

    p->next = pHead;
    return pHead;
}

/*
* 是否为循环链表？
* 思路：选2个节点，分别为慢节点和快节点，慢节点走一步，而快节点走两步，如果快节点能够追上慢节点，则此链表是闭环链表；
*       如果快节点不能追上慢节点，则此链表是开环链表。
*/
ListNode *CompleteList::ClosedLoopList(ListNode *pHead)
{
    if (pHead == nullptr) {
        return nullptr;
    }

    ListNode * pSlowNode = pHead->next;
    if (pSlowNode == nullptr) {
        return nullptr;
    }

    ListNode * pFastNode = pSlowNode->next;
    while (pSlowNode != nullptr && pFastNode != nullptr) {
        if (pSlowNode == pFastNode) {
            return pFastNode;
        }

        pSlowNode = pSlowNode->next;
        pFastNode = pFastNode->next;
        if (pFastNode->next != nullptr) {
            pFastNode = pFastNode->next;
        }
    }
    return nullptr;
}

/*
* 环链表的个数
* 思想：头节点与下一个节点进行比较，若不相等，则个数自加，且向下移位；若相等，则输出环链表的个数。
* 步骤： 
* 第一步：会面节点指向头节点，且链表个数为1；
* 步骤二： 当头节点的下一个节点不等于会面节点，则个数自加且头节点向下移位；
* 第三步：输出链表的个数
*/
int CompleteList::counterClosedLoopList(ListNode *pHead)
{
    if (pHead == nullptr) {
        return 0;
    }

    ListNode *pMeetNode = pHead;
    int count = 1;
    while (pHead->next != pMeetNode) {
        count++;
        pHead = pHead->next;
    }
    return count;
}

void CompleteList::ShowClosedLoopList(ListNode *pListNode) const
{
    ListNode *pHeadNode = pListNode;
    for (int i = 0; i < 10; i++) {
        std::cout<<" "<<pHeadNode->data;
        pHeadNode = pHeadNode->next;
    }
    std::cout << std::endl;
    return;
}

/*
* 闭环的入口 方法一
* 1. 判断链表是否有环
* 思想：可以设置快慢指针，快指针一次走两步，慢指针一次走一步，如果快指针追上了走的慢的指针，那么链表有环；
*       如果走到了链表尾部都没有追上，说明链表无环；
* 2. 如果有环，返回入口节点
* 思想：返回的节点一定在环内，如果计算出环中节点的个数count,快指针比慢指针多走count步，那么两个指针相遇时，
*       就是环的入口节点。
* 步骤：
* 第一步：慢指针走一步，快指针走两步，计算单链是否有环？
* 第二步：如果没有环，则输出为空；如果有环，则计算环的个数n；
* 第三步：前指针向后移动n位, 再查找前指针与后指针是否相等，若相等，则位入口节点，反之。
*/
ListNode *CompleteClosedLoopListFirst::EntryClosedLoopList(ListNode *pHead) 
{
    if (pHead == nullptr || pHead->next == nullptr) {
        return nullptr;
    }

    CompleteList completeList;
    ListNode *pMeetNode = completeList.ClosedLoopList(pHead);
    if (pMeetNode == nullptr) {
        std::cout<<"the closed pHeadNode Node is null"<<std::endl;
        return nullptr;
    } else {
        std::cout<<"the closed pHeadNode Node is "<<pMeetNode->data<<std::endl;
    }
    int nums = completeList.counterClosedLoopList(pMeetNode);
    if (nums == 0) {
        std::cout<<"the nums of closed pHeadNode is zero"<<std::endl;
        return nullptr;
    } else {
        std::cout<<"the nums of closed pHeadNode is "<<nums<<std::endl;
    }

    ListNode *pFastNode = pHead;
    ListNode *pSlowNode = pHead;
    for (int i = 0; i < nums; i++) {
        pFastNode = pFastNode->next;
    }

    while (pFastNode != pSlowNode) {
        pFastNode = pFastNode->next;
        pSlowNode = pSlowNode->next;
    }
    return pFastNode;
}


/*
* 闭环的入口 方法二
* a、第一步，找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，
*    直到fast==slow找到在环中的相汇点。
* b、第二步，找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,
*    设环中有n个节点，fast比slow多走r圈有2x=rn+x; x=rn;（r为圈数，n为一圈的结点数）
* 可以看出slow实际走了多个环的步数，再让fast指向链表头部，slow位置不变。
* 假设链表开头到环接口的距离是y，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，
* 那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = rn，即此时slow指向环的入口。
*/
ListNode *CompleteClosedLoopListSecond::EntryClosedLoopList(ListNode *pHead) 
{
    if (pHead == nullptr || pHead->next == nullptr) {
        return nullptr;
    }
    /*
    ListNode *pSlowNode = pHead;
    ListNode *pFastNode = pHead;
    while (pSlowNode != nullptr && pFastNode->next != nullptr) {
        pSlowNode = pSlowNode->next;
        pFastNode = pFastNode->next->next;
        if (pSlowNode == pFastNode) {
            pFastNode = pHead;
            while (pSlowNode != pFastNode) {
                pSlowNode = pSlowNode->next;
                pFastNode = pFastNode->next;
            }
            return pFastNode;
        }
    }
    */
    ListNode *pSlowNode = pHead->next;
    ListNode *pFastNode = pSlowNode->next;
    while (pSlowNode != nullptr && pFastNode != nullptr) {
        pSlowNode = pSlowNode->next;
        pFastNode = pFastNode->next->next;
        // 当快指针 与 慢指针相遇时
        if (pSlowNode == pFastNode) { 
            pFastNode = pHead; 
            // 当快指针 与 慢指针相遇时
            while (pSlowNode != pFastNode) {
                pSlowNode = pSlowNode->next;
                pFastNode = pFastNode->next;
            }
            return pFastNode;
        }
    }
    return nullptr;
}


int main()
{
    CompleteList completeList;
    std::vector<ListNode *> pCompleteNode;
    for(int i = 0; i < 4; i++) {
        ListNode *completeNodeTemp = completeList.CreateClosedList();
        pCompleteNode.push_back(completeNodeTemp);
    }
    std::cout<<"CreateList1： "<<std::endl;
    completeList.ShowClosedLoopList(pCompleteNode[0]);
    completeList.ShowClosedLoopList(pCompleteNode[1]);


    CompleteClosedLoopListTemp<CompleteClosedLoopListFirst> completeClosedLoopListFirst;
    ListNode *pEntryNode1 = completeClosedLoopListFirst.EntryClosedLoopList(pCompleteNode[0]);
    if (pEntryNode1 == nullptr) {
        std::cout<<"the first entry node of closed pHeadNode is null"<<std::endl;
    } else {
        std::cout<<"the first entry node of closed pHeadNode is "<<pEntryNode1->data<<std::endl;
    }

    int num1 = 2;
    ListNode *pNewNode1  = new ListNode(num1);
    pNewNode1->next = nullptr;
    ListNode *pEntryNode1_2 = completeClosedLoopListFirst.EntryClosedLoopList(pNewNode1);
    if (pEntryNode1_2 == nullptr) {
        std::cout<<"the first entry node of closed pHeadNode is null"<<std::endl;
    } else {
        std::cout<<"the first entry node of closed pHeadNode is "<<pEntryNode1_2->data<<std::endl;
    }

    CompleteClosedLoopListTemp<CompleteClosedLoopListSecond> completeClosedLoopListSecond;
    ListNode *pEntryNode2 = completeClosedLoopListSecond.EntryClosedLoopList(pCompleteNode[1]);
    if (pEntryNode2 == nullptr) {
        std::cout<<"the second entry node of closed pHeadNode is null"<<std::endl;
    } else {
        std::cout<<"the second entry node of closed pHeadNode is "<<pEntryNode2->data<<std::endl;
    }

    int num2 = 3;
    ListNode *pNewNode2  = new ListNode(num2);
    pNewNode2->next = nullptr;
    ListNode *pEntryNode2_2 = completeClosedLoopListSecond.EntryClosedLoopList(pNewNode2);
    if (pEntryNode2_2 == nullptr) {
        std::cout<<"the second entry node of closed pHeadNode is null"<<std::endl;
    } else {
        std::cout<<"the second entry node of closed pHeadNode is "<<pEntryNode1_2->data<<std::endl;
    }
    return 1;  
}