3.11程序改错编程之美问题扩展

判断一个单链表是否有环的算法基本思想是：从头接点开始设两个指针，一个指针为一步一步的走，也就是p=p->next， 而另一个指针是一次走两步，所以是相差一步，如果有环，则会在环上打圈，这样走两步的指针总有机会再一次和一步一步走的指针相遇，一楼的程序中，两个指针都是一步一步走，所以有错，应该将一个指针走两步。另外还要说明的是得到的指针不一定指向环开始的地方，只能说是环上的指针，因为步长只差一步，但是什么时候赶上却不确定，原来的程序中的for(;;) 可能会导致死循环：

LinkedList* IsCyclicLinkedList(LinkedList *pHead) 
{ 
  LinkedList *pCur=pHead; //走一步的
  LinkedList *pStart=pHead; //走两步的

  while(pCur != NULL) 
  { 
  //for(;;) 
  //能够走到NULL，则没有环，此处的判断是因为后面pStart->pNext->pNext会出错。
  if(pStart->pNext ==NULL)  
  return NULL;
  pStart=pStart->pNext->pNext;//走两步
  pCur=pCur->pNext;//走一步

  if(pStart == pCur) 
  return pStart; 
  } 
  return NULL; //能够跳出while，说明一定没有环了，
}