c - 在链表中检测多个循环

我想在下列情况下检测环路

1-2-3-4-5
|----------| ===> case 1

1-2-3-4-5
|-------|    ===> case 2

在情况1循环检测算法工作正常，但不适用于情况2。
我对案例2进行了试运行，发现兔子指针末端正常。
另外，我认为案例2不是有效的单链表，因为它包含2个下一个指针。
我的假设对案例2正确吗？
整个场景是针对单链表的？

最佳答案

以下是不涉及分配堆内存的循环检测解决方案：

struct Node {
   int val;
   struct node * next;
};

bool containsCycle(Node * head)
{
   Node * walker = head;
   NOde * fastWalker = head;
   while(walker && fastWalker)
   {
      fastWalker = fastWalker->next;
      if(walker == fastWalker)
         return true;
      if(fastWalker)
        fastWalker = fastWalker->next;
      if(walker == fastWalker)
         return true;
      walker = walker->next;
   }
   // Fell out of the loop, no cycle
   return false;
}

这个算法使用两个指针，以不同的速度前进如果列表中有一个循环，则两个指针将在一个点上彼此相等。

关于c - 在链表中检测多个循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11875659/