Offer150-23:链表中环的入口节点

题目描述:如果一个链表中包含环，找了环的入口节点。例如，在下图所示的链表中，环的入口节点是节点4。

分析：第一步需要确定一个链表中是否包含环，可以用快慢指针来解决这个问题。定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果快指针追上了慢指针，说明链表中包含环路；如果快指针走到了链表的结尾(指向NULL)那么链表中就不包含环。

        第二步是找到环的入口。我们还可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头节点。如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针再以相同的速度向前移动。当P2指向环的入口节点时，P1也已经围绕着环走了一圈又回到了环的入口节点处。

        那么我们就需要先获得环中的节点的数量n。开始我们判断链表中是否存在环路时，定义了两个指针，当快慢指针重合时，说明两个指针都在环中，链表中存在环路。这时，让一个指针再在环路里走一圈，同时统计它走过的步数，直到它再次回到出发位置，这时我们就可以得到整个环路中节点的数量n的大小。

代码:

ListNode* MeetingNode(ListNode* pHead){if(pHead == nullptr)return nullptr;ListNode* pSlow = pHead;ListNode* pFast = pSlow->m_pNext;while(pFast != nullptr && pSlow != nulltpr){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和pNode2ListNode* pNode2 = pHead;while(pNode1 != pNode2){pNode1 = pNode1->m_pNext;pNode2 = pNode2->m_pNext;}return pNode1;
}