0

I want to detect loop in following cases 

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

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

In case 1 cycle detection algorithm works correctly but not for case 2. I did dry run for case 2 I found that hare pointer ends normally. Also I thought that case 2 is not valid singly linked list as it contains 2 next pointer. Is my assumption correct for case 2? The whole scenario is for singly linked list?

4

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

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

于 2012-08-09T04:54:39.687 回答
1

我将根据您所要求的一系列假设给出答案。

我猜你的格式搞砸了，你正在使用一个由节点结构构建的单链表，该节点结构有一个名为“next”的指针。

我还假设您有一个指向列表第一个元素的指针，称为 Root。

接下来，我假设您的算法包括存储根的副本，然后遍历列表以查看您是否回到根。

这将适用于以下情况：

A -> B -> C -> D -> E   //and E -> A.

但如果

A -> B -> C -> D -> E   //and E -> B.

一种方法是在您行走时标记每个访问过的节点，或者通过在结构中添加一个新字段，或者保留一个哈希表，然后查看是否获得了重复元素。

（实际上，您可以只将每十个节点添加到哈希表中，但根据哈希表检查每个访问的节点是否有重复项）。

如果您提前知道链表中有多少元素（并且它没有被修改），那么简单地走很多次，看看下一个节点是否为空。

于 2012-08-09T04:20:41.890 回答