霜之哀伤

一个大公司的面试题（具体哪个公司不记得了），面试官就这么问在坐的面试者：“怎样判断一个链表里是否存在循环链表？”
很简单的一个题，有人立马就给出答案：“遍历整个链表，每到一个节点都做个标记，看后来标记是否存在。”
然后面试官说：“我的每个节点都有严格的意义，不能改变其中任何内容和标记？”
面试者也能很快就给出答案：“再定义一个数组来标记！”
面试官又加上限制：“我的电脑内存有限，无法再分配这么多的空间！”
面试者有的能给出答案：“用两个指针p1,p2，p1从第一个节点开始分别和后面所有节点比较（用p2），如果p2和p1相等了说明存在循环！”
不能否定这些答案都是能达到面试官的要求，可是想想，如果面试官不提这么多要求，他们会一步步的改进吗？作为一个程序员，应该自己考虑更多的问题，不应该碰到了才解决。再细想想，最后一个答案能被录用吗，明智点的面试官是不会录用他的了，他这个算法的时间复杂度太高o（N2）。面试最初想要的答案是什么呢？
我们可以这样，定义两个指针p1,p2，先排除只有一个节点的情况，然后p1指向第一个节点，p2指向第三个节点，每次p1向后移一个节点，p2向后移两个节点，如果存在循环，p2总是再能追上p1的，使p1=p2，如果p1或p2=NULL那么就跳出循环，不存在循环了。
所以一个算法的设计，是需要从各方面考虑的，并不需要我们马上就写，那只是一个低级别的程序员做的事，一个程序员是不能偷懒的，你偷懒了，电脑就得忙着了，电脑忙着了，用户就要找你麻烦了。把这个算法写了一下，给大家参考参考：

bool research_cycleLink(NODE* headNode)
{
    NODE* p1, p2;
    bool result = false;//返回链表是否带有循环

    p1 = headNode;
    if (p1->next == NULL)
    {
        printf("只存在一个节点！\n");
    }
    else
    {
      p2 = (p1->next)->next;//p2指向第三个节点
      while((p1 != NULL) && (p2 != NULL))
      {
          if (p1 == p2)
          {
              //p2赶上p1则链表带有循环
            result = true;
            break;
          }
          else
          {
            p1 = p1->next;//p1向后移一个节点
            p2 = (p2->next)->next;//p2向后移两个节点
          }
      }//end while
    }
    return result;
}