题目
如果一个链表中包含环，如何找出环的入口节点？例如：在下图所示的链表中，环的入口节点是节点3
分析
- 1、如何确定一个链表中包含环？
可以使用两个指针来解决这个问题。定义两个指针，同时从头结点出发，一个指针一次走一步，一个指针一次走两步。如果走的快的指针追上了走的慢的指针，那么链表就包含环；如果走的快的指针走到链表末尾（m_pNext为NULL）都没有追上第一个指针，那么链表就不包含环
- 2、如何找到环的入口？
定义两个指针P1和P2指向链表的头结点。如果链表中的环有n个结点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时，第一个指针已经围绕环走了一圈，又回到了环的入口
由图可知
1、指针P1和P2在初始化时都指向链表的头结点
2、由于环中有4个结点，所以指针P1先在链表上向前移动4步
3、指针P1和P2以相同的速度在链表上向前移动，直到它们相遇，相遇的结点就是环的入口
- 3、如何得到环中结点的数量？
在前面提到判断一个链表里是否有环时用到了一块一慢的两个指针，如果两个指针相遇，则表明链表中存在环。两个指针相遇的结点一定是在环中。可以从这个结点出发，一边继续向前移动一边计数，当再次回到这个结点时，就可以得到环中结点数了
算法实现
定义链表
struct ListNode {
int m_nValue;
ListNode *m_pNext;
};
MeetingNode函数在链表中存在环的前提下找到一块一慢两个指针相遇的结点
// 是否有环
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 = 1; // 环中结点的数目
ListNode *pNode1 = meetingNode;
while (pNode1->m_pNext != meetingNode) { // 遍历环内某一结点计算环的结点个数
pNode1 = pNode1->m_pNext;
++nodesInLoop;
}
// 先移动pNode1，次数为环中结点的数目
pNode1 = pHead;
for (int i=0; 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;
}
断链法
时间复杂度为O（n）
两个指针，一个在前面，另一个紧邻着这个指针，在后面。 两个指针同时向前移动，每移动一次，前面的指针的next指向NULL。 也就是说：
访问过的节点都断开，最后到达的那个节点一定是尾节点的下一个， 也就是循环的第一个。
这时候已经是第二次访问循环的第一节点了，第一次访问的时候我们已经让它指向了NULL， 所以到这结束。但是这种方法修改了链表的指向
算法实现
ListNode * EntryNodeOfLoop2(ListNode *pHead) {
if (pHead == nullptr ||pHead->m_pNext == nullptr)
return nullptr;
// 下一个结点
ListNode *previuosNode = pHead;
// 当前结点
ListNode *currentNode = pHead->m_pNext;
// 是否有环认证，无环返回
if (MeetingNode(pHead) == nullptr)
return nullptr;
// 确保有环的前提之下才行，如果本身无环，那么程序执行失败。
while (currentNode != nullptr) {
previuosNode->m_pNext = nullptr;
previuosNode = currentNode;
currentNode = currentNode->m_pNext;
}
return previuosNode;
}
使用集合
这里用到了STL中的set，set有一个特性就是不能插入相同元素，这样只需遍历原List一次就可以判断出有没有环，还有环的入口地址。s.insert(node).second这里在插入的同时也判断了插入是否成功，如果不成功表明set中已经有该元素了，该元素就是环的入口元素。
ListNode* EntryNodeOfLoop3(ListNode* pHead)
{
set<ListNode*> set;
ListNode* node = pHead;
while(node!= NULL){
if(set.insert(node).second)
node = node->m_pNext;
else
return node;
}
return node;
}
参考
《剑指offer》
链表中环的入口结点
