offer_23

//面试题23：链表中环的入口节点
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;
  
  ListNode* pNode2=pHead;
  while(pNode1!=pNode2){
    pNode1=pNode1->m_pNext;
    pNode2=pNode2->m_pNext;
  }
  return pNode1;
}


//在链表中存在环的情况下找到快慢指针相遇的节点
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;
   }
}