单向链表是否有环问题(C)

     问题描述：在单向链表中，每个结点都包含一个指向下一个结点的指针，最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点，就会形成一个环，在顺序遍历链表的时候，程序就会陷入死循环。如何检测一个链表中是否有环，如果检测到环，如何确定环的入口点（即求出环长，环前面的链长）。
      一种比较耗空间的做法是，从头开始遍历链表，把每次访问到的结点（或其地址）存入一个集合（hashset）或字典（dictionary），如果发现某个结点已经被访问过了，就表示这个链表存在环，并且这个结点就是环的入口点。这需要O(N)空间和O(N)时间，其中N是链表中结点的数目。
     如果要求只是用O(1)空间、O(N)时间，应该怎么处理呢？

 

int   is_link_list_cicled(Node*   head)
{
        Node   *p   =   head,   *q   =   head-> next;
        while(p   &&   q)
        {
                if(p   ==   q)
                        return   1;
                p   =   p-> next;
                q   =   q-> next;
                if(!q)
                        return   0;
                q   =   q-> next;
        }
        return   0;
}

 

证明：

 

证明步长法的正确性(追击问题，如果有环则肯定可以相遇)：

如果链表有环，不妨假设其环长度为M（>=2）。
p指针首次到达交点（N0）时，q指针已经进入环。
设p=0;q=q-p;
再进过i(i>=0)步后，p=(p+i)%m；q=(q+2*i)%m；
则必存在一个i使得(p+i)%m = (q+2*i)%m。(p,q 都为常数)。

 

问题描述参考：

GoCalf 的Blog