使用两个查找列表在 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;
   }
}