读书人

判断单向链表中是不是有环

发布时间: 2012-12-25 16:18:29 作者: rapoo

判断单向链表中是否有环
用两个速度不一样的指针从头遍历,如果存在环,则快的指针终将追上慢的指针!

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);
}

读书人网 >编程

热点推荐