c - 使用两个指针在 C 中查找列表是否是非循环的 - 为什么要与 faster->next 进行比较？

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