最新消息:20190717 VPS服务器:Vultr新加坡,WordPress主题:大前端D8,统一介绍入口:关于

判断单链表中是否有环

工作和技术 crifan 693浏览 0评论

已知:
一个单链表,写一函数判断其中是否存在环
单链表如下:
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()

注:以待补充。

转载请注明:在路上 » 判断单链表中是否有环

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. 路过,我是C++爱好者,有时间多多交流,呵呵。
    guodong12412年前 (2008-05-20)回复
  2. 不错,学习了!
    fcbdf12年前 (2008-04-26)回复
59 queries in 0.243 seconds, using 18.83MB memory