百度空间 | 百度首页 
 
查看文章
 
[zt]快慢法判断单链表中是否有循环链表
2006-08-30 18:01

题目:写个算法,判断在一个单向链表中是否存在循环链表。

有个经典的算法就是解决这个问题的,好象是叫快慢法.他的原理是,如果A,B两人从同一地点出发,B的速度大于A,那么如果存在一个环的话,B和A肯定是能再见面的.

bool IsLoop( link* head)
{
   link* s = head; //移动缓慢的指针
   link* f = head; //移动快速的指针

   
   do
   {
      if( s == NULL ) return (false );
      s = s->next; //一次向前移动一个
     
      if( f== NULL ) return (false );
      f = f->next;
    
      if( f== NULL ) return (false );
      f = f->next; //一次向前移动2个
   }while( f!= s);

   return (f!=NULL);
}


类别:Computer | 添加到搜藏 | 浏览() | 评论 (0)
 
最近读者:
 
网友评论:
发表评论:
姓 名:
网址或邮箱: (选填)
内 容:
验证码: 请点击后输入四位验证码,字母不区分大小写
      

     

©2009 Baidu