找出链表是否有循环[代码战争问题]

Question

bool hasCycle(Node * head)
{
Node *p = NULL;
Node *q = head;

while(q)
{
q = q->next;
if(q->next != NULL) q = q->next;
p = p->next;
}
return p == q ? true : false;
}

我的代码适用于大多数解决方案，但由于某种原因，它在一个测试用例中失败了。有人能看看我的代码并向我解释我的逻辑出了什么问题吗。这是代码战争的链接https://www.codewars.com/kata/5af9a4b2de4c7fdab30000e5/train/cpp

Answer 1

这个问题背后的逻辑是使用两个指针：一个是快，一个是慢。如果存在循环，则fast将赶上slow。如果没有环路，则fast将首先到达终点。

您的代码没有像这样排除逻辑。我不知道你想做什么。这是我的代码：

bool hasCycle(Node * head)
{
Node *fast = head, *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) return true; // here the fast catches the slow
}
return false; // here the fast reaches the end of the linked list
}