判断一个单链表是否有环的算法基本思想是:从头接点开始设两个指针,一个指针为一步一步的走,也就是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) |