大家帮我看看这个判断链表中是否有环的程序对吗？

Kandada1985 2009-01-14 01:08:11

刚才发帖子昏了头，所以又发一帖，希望大家帮看看吧
我不懂的地方是：
node *low = head;
node *fast= head->next;
网上提供的思路是附设2个指针，都指向头结点，一个快，一个慢
慢的走一步，快的一次走两步，可是这个网上找到的怎么是node *fast= head->next呢？
不太懂，希望大家给指点下迷津，谢谢啊



bool CheckCircle( const node *head)

{

   if(head == null)   return false;

   node *low = head;

   node *fast= head->next;

   while(fast!=null && fast->next!=null)

   {

      low = low->next;

      fast = fast->next->next;

      if(low == fast)

         return true;

   }

   return false;

}

...全文

394 13 打赏收藏转发到动态举报

写回复

用AI写文章

13 条回复

切换为时间正序

请发表友善的回复…

发表回复

xiabeizi 2009-07-22

打赏
举报

mark yi xia!

maxzhuang 2009-03-05

打赏
举报

可以参阅
http://www.cnblogs.com/maxz/archive/2009/03/04/1403170.html

Kandada1985 2009-01-18

打赏
举报

谢谢dlyme,我理解了，以前都是背程序，现在看来，在理解的基础上写才是正解
非常感谢，看来我得好好看看算法了

na2650945 2009-01-14

打赏
举报

[Quote=引用 3 楼 dlyme 的回复:]
这段代码没问题，完全能够正确判断出链表中是否有环存在。
学习的时候要注意真正理解其中的原理~

假设该链表在环出现之前有L个结点，环中有C个结点。
再假设慢指针初始化时指向的位置为a、快指针初始化时指向的位置为b，
如果二者在t次移动后相遇，也就是说：(a+t-L) mod C == (b+2*t-L) mod C
稍微变形一下就可以看出，t==a-b(mod C)这个模线性方程一定有解
所以无论a、b的起始位置如何，二者总是会相遇的。

…
[/Quote]
学习了。

chin_chen 2009-01-14

打赏
举报

呵呵，同意楼上的！
ps：我只是就这个代码而说的，只要快的比慢的只快一步，那么在任何的情况下都适用的。

大王派我去巡山 2009-01-14

打赏
举报

[Quote=引用 6 楼 chin_chen 的回复:]
两个人跑步，如果有回路，两个人就在那打转，当然总有一天，快得（ fast = fast->next->next;）会追上慢的（low = low->next;）
[/Quote]
现实生活中固然是这样。但这个例子是个离散模型，所以不能这么想当然。

比方说：假设链表是由4个结点首尾相接构成的一个圆圈（编号为0~3）
慢指针初始位置在0，每次前进1步；
快指针初始位置在3，每次前进3步；
虽然这两个指针也是一快一慢一前一后，但它们永远也不会相遇！

说到底就是要保证模线性方程有解，所以前面也说了“快慢指针的步长选择很重要”。
楼主的代码里慢指针每次前进1步、快指针每次前进2步，这样是肯定能够相遇的。

chin_chen 2009-01-14

打赏
举报

两个人跑步，如果有回路，两个人就在那打转，当然总有一天，快得（ fast = fast->next->next;）会追上慢的（low = low->next;）

nullah 2009-01-14

打赏
举报

hmsuccess 2009-01-14

打赏
举报

大王派我去巡山 2009-01-14

打赏
举报

这段代码没问题，完全能够正确判断出链表中是否有环存在。
学习的时候要注意真正理解其中的原理~

假设该链表在环出现之前有L个结点，环中有C个结点。
再假设慢指针初始化时指向的位置为a、快指针初始化时指向的位置为b，
如果二者在t次移动后相遇，也就是说：(a+t-L) mod C == (b+2*t-L) mod C
稍微变形一下就可以看出，t==a-b(mod C)这个模线性方程一定有解
所以无论a、b的起始位置如何，二者总是会相遇的。

这种方法之所以能够判断链表中是否有环，是要使快、慢指针在环里转圈的时候总会碰面。
所以快慢指针的步长选择很重要，起始位置倒是无关紧要的事情。