c - 这段代码如何在链表中查找循环？

Question

这个问题已经有答案了:

已关闭 12 年前。

Possible Duplicate:
Best algorithm to test if a linked list has a cycle

p=head;

q=head->next;
while(p!=NULL && q!=NULL)

{

if(p==q) { //Loop detected! exit(0); }

p=p->next;

q=(q->next)?(q->next->next):q->next; --how this line works ??

}

Answer 1

首先，如果列表中没有循环，则条件 p==q 永远不会为真，因为 q 始终“领先”于 p。

然后，p 和 q 之间的距离在每次迭代时增加 1。因此，如果存在循环，只要距离是循环长度的整数倍，条件 p==q 就会为真。

相关行将 q 向前移动 2 个位置。它首先检查 q 在向前移动一个位置后是否不会到达列表末尾，以避免空指针取消引用。 (q->next 是 q 前面一个位置，q->next->next 是前面两个位置。)