c - 使用两个指针查找列表是否在 C 中是非循环的 - 为什么与更快->下一个比较？

Question

我知道，给定一个链表，如果我们想找出它是否是非循环的，我们可以有两个指针以不同的速度在链表中运行。然后如果我们比较快和慢的值并且两者相同，我们知道列表是循环的。但是，我看到人们还将较慢的指针与下一个较快的指针进行比较。像这样的代码：

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;
      }
   }
}

为什么这个条件是必要的：faster->next == slower?? 仅此还不够：faster == slower

谢谢

Answer 1

这不是必需的。如果faster->next == slower成立，faster == slower将在下一次迭代中成立。

但是，您发布的代码仍然不正确，因为在第一次迭代中两个指针总是相等的。正确的代码是：

bool findCircular(Node *head)
{
   Node *slower = head;
   Node *faster = head;
   while(true) {
     // if the faster pointer encounters a NULL element
     if( !faster || !faster->next)
         return false;
     slower = slower->next;
     faster = faster->next->next;

     //if both pointers are ever equal, it's a circular list
     if (faster == slower)
         return true;
   }
}