节点上的链表操作(floyd循环检测)

Question

结构

SinglyLinkedListNode {
int data;
SinglyLinkedListNode* next;
};

功能

bool has_cycle(SinglyLinkedListNode* head) {
SinglyLinkedListNode* s=head,*f=head->next;
while(s != NULL && f != NULL && f->next != NULL)
{
s = s->next;
f = f->next->next;
if(s->data == f->data)
return true;
}
return false;
}

根据该算法，如果慢指针s和快指针f到达同一节点，则称该列表具有循环。我假设同一个节点会有相同的数据，但为什么我会得到失败的测试用例？

当我将(s->data = f->data)更改为(s == f)时，它工作正常。s == f和s->data == f->data之间有什么区别

Answer 1

这里的主要问题是您的最终检查条件。在(循环中(可能存在重复的测试用例中，这将失败。当您检查"；"相同节点"；检查指针值是否相同更好，因为它总是唯一的，即每个节点都有一个唯一的地址，但对于节点包含的值，它不必为真。例如：

1->3->4->5->6->4->7->空

//注意给出相对索引(第0、第1、…和随机寻址以便于理解(

迭代1:s在1(第0个节点，1000010092(，而f在3(第1个节点，21983193(

迭代2:s在3(第一个节点，21983193(，而f在5(第三个节点，129764714(

迭代3:s在4(第二个节点，12984124(，而f在4(第一个节点，149284124(

看到歧义了！！

即使你的算法给出了TRUE，循环也不存在。但如果你通过地址进行检查，这种假阳性就不会发生。提示：检查任何问题中是否存在重复，它们往往会被添加以引发此类问题。