单向链表是否有环问题(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