38

如何确定单链表是否是循环/循环的？我试图搜索，但找不到满意的解决方案。如果可能，您能否提供伪代码或 Java 实现？

例如：
1→ 3→ 5→ 71→ 45→ 7→ 5，其中第二个5实际上是列表的第三个元素。

4

12 回答 12

78

标准答案是在开始时采用两个迭代器，第一个递增一次，第二个递增两次。检查它们是否指向同一个对象。然后重复，直到增加两次的那个到达第一个或到达末尾。

该算法在列表中找到任何循环链接，而不仅仅是一个完整的循环。

伪代码（不是 Java，未经测试——从我的脑海中浮出水面）

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
   }
}
于 2009-07-09T12:31:01.340 回答
16

一种称为Floyd 算法的简单算法是有两个指针 a 和 b，它们都从链表中的第一个元素开始。然后在每个步骤中，您将 a 增加一次，将 b 增加两次。重复直到到达列表的末尾（无循环）或 a == b（链接列表包含循环）。

另一种算法是布伦特算法。

于 2011-02-05T10:31:25.280 回答
8

我知道的三个主要策略：

  1. 开始遍历列表并跟踪您访问过的所有节点（例如，将它们的地址存储在地图中）。您访问的每个新节点，检查您是否已经访问过它。如果您已经访问过该节点，那么显然存在一个循环。如果没有循环，你最终会到达终点。这不是很好，因为存储额外信息的空间复杂度为 O(N)。

  2. 乌龟/野兔解决方案。在列表的前面开始两个指针。第一个指针，“乌龟”每次迭代向前移动一个节点。另一个指针“Hare”每次迭代向前移动两个节点。如果没有循环，兔子和乌龟都会到达列表的末尾。如果有一个循环，野兔会在某个时候通过乌龟，当这种情况发生时，你就知道有一个循环。这是 O(1) 空间复杂度和一个非常简单的算法。

  3. 使用该算法反转一个链表。如果列表有一个循环，您将在尝试反转它时回到列表的开头。如果它没有循环，您将完成反转并结束。这是 O(1) 的空间复杂度，但算法略丑。

于 2011-02-05T10:32:10.493 回答
4

我计算你的节点并再次到达 *head。

于 2011-02-05T10:31:17.523 回答
2

使用龟兔算法。

于 2009-07-09T12:42:18.863 回答
2

下面的方法怎么样：

按照任何标准算法按升序对链接列表进行排序。排序前：4-2-6-1-5 排序后：1-2-4-5-6

排序后，检查每个节点数据并与链接节点的数据进行比较，如下所示：

如果（当前代码->数据>当前节点->链接->数据）即循环=真；

在任何比较中，如果排序链表的“currentnode->data”中的任何一个大于“currentcode->link->data”，则表示当前节点指向某个先前的节点（即循环）；

伙计们，我没有设置来测试代码。如果这个概念有效，现在让我看看。

于 2013-05-03T10:04:44.097 回答
1

一个算法是：

  1. 存储指向第一个节点的指针
  2. 遍历链表比较每个节点指针和这个指针
  3. 如果你遇到一个 NULL 指针，那么它不是循环链表
  4. 如果您在遍历时遇到第一个节点，则它是一个循环链表
于 2011-02-05T10:33:58.747 回答
0

从一个节点开始并记录它，然后遍历整个列表，直到您到达一个空指针或您开始使用的节点。

就像是：

Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
   if(temp == start)
   {
     circular = true;
     break;
   }
   temp = temp->next;
}
return circular

这是 O(n)，这几乎是你可以通过单链表获得的最好的（如果我错了，请纠正我）。

或者要查找列表中的任何循环（例如中间），您可以执行以下操作：

Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
   if(array.contains(temp) == true)
   {
     circular = true;
     break;
   }
   array.insert(temp);
   temp = temp->next;
}
return circular

由于动态数组的插入时间，这会有点慢。

于 2009-07-09T12:31:00.870 回答
0

@samoz 在我看来有答案！伪代码丢失。会是这样的

yourlist 是你的链表

allnodes = hashmap
while yourlist.hasNext()
   node = yourlist.next()
   if(allnodes.contains(node))
      syso "loop found"
      break;
   hashmap.add(node)

抱歉，代码非常伪（最近做的脚本比 Java 多）

于 2009-07-09T12:36:04.273 回答
0

这是一个不错的站点，可以在其上复制不同的解决方案。

查找循环单链表

这是该网站上的获胜者

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

这个解决方案就是 Robert W. Floyd 于 1967 年在“Non-deterministic Algorithms”中发表的“Floyd's Cycle-Fiding Algorithm”。它也被称为“The Tortoise and the Hare Algorithm”。

于 2009-07-09T12:42:55.257 回答
0

它永远不会从循环中终止，也可以在以下解决方案中完成：

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
      if(i.next()==j)
          break;
    }
}
于 2010-07-15T14:31:20.980 回答
0

试试这个

/* Link list Node */

结构节点 { int 数据；下一个结构节点*；};

/* 如果给定的链表是循环的，这个函数返回真，否则返回假。*/ bool isCircular(struct Node *head) { // 一个空链表是循环的 if (head == NULL) return true;

// Next of head
struct Node *node = head->next;

// This loop would stope in both cases (1) If
// Circular (2) Not circular
while (node != NULL && node != head)
   node = node->next;

// If loop stopped because of circular
// condition
return (node == head);

}

于 2016-08-19T10:48:12.597 回答