判断一个单向链表中是否存在环

方法一：使用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;}