判断一个单向链表中是否存在环 - c++编程基础

方法一：使用map来记录链表中的结点是否被访问，若存在被访问两次的结点则说明存在环。

#include "iostream"  
#include "map"  
using namespace std;  
mapm;  
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;  
}