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

Question

我想在以下情况下检测循环

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

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

在案例 1 中，循环检测算法工作正常，但在案例 2 中却没有。 我对案例 2 进行了试运行，我发现 hare 指针正常结束。 我还认为案例 2 不是有效的单链表，因为它包含 2 个下一个指针。 我的假设对案例 2 是否正确？ 整个场景是针对单链表的？

Answer 1

这是一个不涉及分配堆内存的循环检测解决方案:

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

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