怎么判断一个单链表是否形成一个环？

Question

怎么判断一个单链表是否形成一个环？包括局部的环！要求时间复杂度O(n),空间尽量小！

Answer 1

while(结点->next!=NULL)
{ 
  if (结点->next->数据==头结点->数据) break;
  结点=结点->next;}

Answer 2

while(结点->next!=NULL)
{ 
  if (结点->next->数据==头结点->数据) break;
  结点=结点->next;}不可以吧，加入第n个节点与头结点的数据相同？？
while(结点->next!=NULL)
{ 
  if (结点->next==头结点->next) break;
  结点=结点->next;}应该判断指向是否相同！

Answer 3

#include <set>
using namespace std;set <Data*> s;DATA* p = pHead;
s.insert(p);
while(p->next != NULL)
{
   p = p->next;
   if(s.find(p) != s.end() 
   {
      //形成环
      break;
   }
   else
       s.insert(p);
}