已知：
一个单链表，写一函数判断其中是否存在环
单链表如下：
struct TNode{char Chval;TNode* PtNext};
bool Check(const TNode* PtHead)
解答：
思路：
有些题目要求：注意不能用标志位，最多只能用两个额外指针
其实也就是要求用下述方法进行解答：
使用两个指针，一个每次移动一步，另一个每次移动两步
如果单链表中存在环，那么他们必将会在环中相遇。
实现：
boolean CheckCycleLink(struct TNode *header)
{
if(header==NULL)
return FALSE;
struct TNode *pFast,*Slow;
//initialization
pFast=header;
pSlow=header;
while(pFast!=NULL&&pFast!=pSlow)
{
pSlow=pSlow->next; //move one step once time
pFast=pFast->next->next; //move two step once time
}
if(pFast==NULL) // the pointer go the the end of this link
return FALSE;
if(pFast==pSlow) //if cylce exist ,the two pointer will meet together finally
return TRUE;
}//CheckCycleLink()
注：以待补充。
转载请注明：在路上 » 判断单链表中是否有环