判断单向链表中是否有环

核心思想 :用两个速度不一样的指针从头遍历,如果存在环,则快的指针终将追上慢的指针!
bool   CircleInList(Link*   pHead)  
  {  
  if(pHead   ==   NULL   ||   pHead->next   ==   NULL)//无节点或只有一个节点并且无自环  
  {  
  return   (false);  
  }  
  if(pHead->next   ==   pHead)//自环  
  {  
  return   (true);  
  }  
  Link   *pTemp1   =   pHead;//step   1  
  Link   *pTemp   =   pHead->next;//step   2  
  while(pTemp   !=   pTemp1   &&   pTemp   !=   NULL   &&   pTemp->next   !=   NULL)  
  {  
  pTemp1   =   pTemp1->next;  
  pTemp   =   pTemp->next->next;  
  }  
  if(pTemp   ==   pTemp1)  
  {  
  return   (true);  
  }  
  return   (false);  
  }

 

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注