c - 寻找循环列表算法的疑惑

Question

我在 C 中有以下代码，它试图查找列表是否是循环的：

bool findCircular(Node *head)
{
   Node *slower, * faster;
   slower = head;
   faster = head;
   while(true) {

     // if the faster pointer encounters a NULL element
     if( !faster || !faster->next)
       return false;
    //if faster pointer ever equals slower or faster's next
    //pointer is ever equal to slow then it's a circular list
     else if (faster == slower || faster->next == slower)
        return true;
     else{
       // advance the pointers
        slower = slower->next;
        faster = faster->next->next;
      }
   }
}

我对它的某些部分有一些疑问。首先，在我们第一次进入 while 循环时，我们不是总是会达到条件（更快 == 更慢）吗？我们已经初始化了更快和更慢，以指向它指向的相同位置。

其次，为什么我们还要比较 if (faster->next == slow)，难道我们还不够 justfaster == slower吗？

Answer 1

实际上，书中打印的代码是不正确的，除非传递了 null 或 1 元素列表，否则将返回 1。勘误表显示了更正的版本。

修复方法是跟踪这是否是第一次循环，并从第二次开始执行循环列表检查：

 int first = 1;  /* New code */
 while (1) {
     if (!faster || !faster->next)
         return 0;
     else if ((faster == slower || faster->next == slower) && !first)  /* New code */
         return 1;
     else {
         slower = slower->next;
         faster = faster->next->next;
         first = 0; /* New code */
     }
 }

（上面的代码使用“faster”和“slower”，就像你的版本一样；书和勘误表使用“fast”和“slow”。）

Answer 2

不要同时从faster和开始。做错误检查并从.slowerheadfasterhead->next

该算法应该在没有faster->next ==slower.