Chinaunix首页 | 论坛 | 博客
  • 博客访问: 171999
  • 博文数量: 27
  • 博客积分: 495
  • 博客等级: 下士
  • 技术积分: 299
  • 用 户 组: 普通用户
  • 注册时间: 2011-09-07 19:22
文章分类

全部博文(27)

文章存档

2013年(4)

2012年(1)

2011年(22)

我的朋友

分类: C/C++

2011-12-03 22:28:35

判断一个单链表是否有环的算法基本思想是:从头接点开始设两个指针,一个指针为一步一步的走,也就是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,说明一定没有环了,
}
阅读(3812) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~

lumia19922015-06-20 16:51:20

就是说修改之后无法得到满足题意的要求了?

yangcheng331202014-05-03 15:55:42

应该是while(pCur != NULL && pStart  != NULL)  吧?