频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
判断一个单向链表中是否存在环
2013-09-12 11:22:16           
收藏   我要投稿
方法一:使用map来记录链表中的结点是否被访问,若存在被访问两次的结点则说明存在环。

 

#include "iostream"  
#include "map"  
using namespace std;  
map<node*,int>m;  
bool IsLoop(node *head)  
{  
      if(!head)  
           return false;  
      node *p=head;  
      while(p)  
     {  
           if(m[p]==0) // 默认值都是0  
                m[p]=1;  
           else if(m[p]==1)  
                return true;  
           p=p->next;  
     }  
}  

 

 

 

 

方法二:设置两个指针pSlow,pFast,慢的一次跳一步,快的一次跳两步,往链表末端移动,若慢指针追上了快指针

,则说明链表存在环。此方法速度很快且不需要额外的存储空间。

 

bool IsLoop(node *head)  
{  
    node *pSlow=head;  
    node *pFast=head;  
    while(pSlow!=NULL && pFast!=NULL)  
    {  
        pSlow=pSlow->next;  
        pFast=pFast->next->next;  
        if(pSlow==pFast)  
           return true;  
    }  
    return false;  
}  

 

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 单向
上一篇:图的一系列算法(待续)
下一篇:uvc摄像头代码解析1
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站