怎么判断链表中是否有环？

1.判断一个单向链表是否有环：
给定链表的头指针：Node*head。
设2个指针，一个指针每次移动1步，另一个指针每次移动2步，如果2个指针相遇那么说明有环，如果有一个指针到NULL了就说明没有环：
bool CircleInList(Link* pHead)
{
if(pHead == NULL || pHead->next == NULL)//无节点或只有一个节点并且无自环
{
return (false);
}
if(pHead->next == pHead)//自环
{
return (true);
}
Link *pTemp1 = pHead;//step 1
Link *pTemp = pHead->next;//step 2
while(pTemp != pTemp1 && pTemp != NULL && pTemp->next != NULL)
{
pTemp1 = pTemp1->next;
pTemp = pTemp->next->next;
}
if(pTemp == pTemp1)
{
return (true);
}
return (false);
}



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

如果链表有环，不妨假设其环长度为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 都为常数)。


2.引申的问题

Finding a duplicated integer(在一个数组里找重复数). Given a read-only array of n integers between 1 and n-1, design an O(n) time algorithm to find a duplicated integer. Use only O(1) space.其实和单链表有环一个道理。