面试题23：链表中环的入口节点。如果一个链表中包含环，如何找出环的入口节点？
解决这个问题的第一步是如何确定一个链表中存在环。我们可以定义两个指针，初始化为指向头节点的指针。两个指针同时从链表头部出发，一个指针一次走一步，另一个指针一次走两步，如果走的快的指针追上了走得慢的指针，那么链表就包含环，如果走得快的指针走到了链表的末尾都没有追上走得慢的指针，那么链表就不包含环。
第二步是找到环的入口，我们还是先定义两个指针P1、P2，都初始化为指向头节点的指针。如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动，当P2指向环的入口节点时，P1已经绕了环一圈又回到了入口节点。
剩下的问题是如何得到环中节点的数目。我们之前分析到一快一慢指针相遇时，一定是在环中，可以此时从这个节点出发，一边向前移动一边计数，当再回到这个节点时，就可以得到环中节点数了：
#include <iostream>
using namespace std;
struct ListNode {
int m_nValue;
ListNode* m_pNext;
};
void AddToTail(ListNode** pHead, int value) { //尾插法
ListNode* pNew = new ListNode(); //为新结点分配内存
pNew->m_nValue = value;
pNew->m_pNext = nullptr;
if (*pHead == nullptr) { //如果是空链表
*pHead = pNew;
}
else {
ListNode* pNode = *pHead;
while (pNode->m_pNext != nullptr) { //找到链表末尾
pNode = pNode->m_pNext;
}
pNode->m_pNext = pNew; //将链表末尾元素的指针指向新节点
}
}
ListNode* MeetingNode(ListNode* pHead) { //判断链表是否有环，如有返回环内一节点，如没有返回nullptr
if (pHead == nullptr || pHead->m_pNext == nullptr) { //有环时链表长度大于1
return nullptr;
}
ListNode* pSlow = pHead, *pFast = pHead->m_pNext;
while (pFast->m_pNext != nullptr) {
pSlow = pSlow->m_pNext;
pFast = pFast->m_pNext;
if (pFast->m_pNext != nullptr) {
pFast = pFast->m_pNext;
}
if (pSlow == pFast) {
return pSlow;
}
}
return nullptr;
}
int NumOfNodesInLoop(ListNode* pNode) { //环中节点数
if (pNode == nullptr || pNode->m_pNext == nullptr) { //防止输入节点没有环且只有一个节点，输入一个节点时以下访问第二个节点的代码就会出错
return -1;
}
ListNode* pNodeMove = pNode->m_pNext;
int count = 1;
while (pNode != pNodeMove) {
if (pNodeMove->m_pNext != nullptr) {
pNodeMove = pNodeMove->m_pNext;
}
else {
return -1;
}
++count;
}
return count;
}
ListNode* EntryNodeOfLoop(ListNode* pHead, int loopLength) { //找环的入口节点
if (pHead == nullptr || loopLength < 2) {
return nullptr;
}
ListNode* pAhead = pHead, * pBehind = pHead;
for (int i = 0; i < loopLength; ++i) {
pAhead = pAhead->m_pNext;
}
while (pAhead != pBehind) {
pAhead = pAhead->m_pNext;
pBehind = pBehind->m_pNext;
}
return pAhead;
}
int main() {
ListNode* pHead1 = new ListNode();
pHead1->m_nValue = 0;
pHead1->m_pNext = nullptr;
AddToTail(&pHead1, 1);
pHead1->m_pNext->m_pNext = pHead1;
ListNode* pResMeetingNode = MeetingNode(pHead1);
if (pResMeetingNode) {
cout << "链表中有环。" << endl;
int numOfNodesInLoop = NumOfNodesInLoop(pResMeetingNode);
cout << "环中的节点数为：" << numOfNodesInLoop << endl;
cout << "环的入口节点值为：" << EntryNodeOfLoop(pHead1, numOfNodesInLoop)->m_nValue << endl;
}
else {
cout << "链表中没有环。" << endl;
}
}