判断一个链表中是否有环

判断一个链表中是否有环

设置两个指针，开始都指向链表头，然后其中一个指针每次向前走一步，另一个指针每次向前走两步，如果快的遇到NULL了，证明该链表中没有环，如果有环，快的指针每次都要比慢的多走一步，最终两个指针会相遇，（注意：这里快指针不会跳过慢指针而不相遇，因为它每次都只比慢指针多走一个单位）
bool judge(list *head){if(head == NULL){return false;//没有环}
list *pFast = head;
list *pSlow = head;
while(pFast-next != NULL && pFast-next-next != NULL){pFast = pFast-next-next;
pSlow = pSlow-next;

问题：给出一个链表，判断是否有环（可能是首尾相连，也可能是中间的某个节点构成环）。这个题最开始想的是输入参数包含一个头节点及这个链表的元素个数，那么这样我们在循环的时候加一个步长就可以了，如果steps>len说明肯定存在环了。但是没说给你元素个数怎么办，只给你个头指针。然后我就想开一个数组记录p指针走过的路径，这样每走过一个节点判断这个地址是否走过，这样的话空间复杂度又不行了。看网上的流行解法吧：步长法：p=head;q=head;while(p && q && q->next){ p=p->next; q=q->next->next; if（p == q） return 1;}return 0;解释：p每次走一步，q每次走2步，这样如果存在循环节，我们假设循环节长度为m，那么肯定存在一个整数i使得(p+i)%m=(q+2*i)%m,这样我们就可以判断是否存在循环节了。这个题可以算是一个拓展思维的好题了。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息