如何高效地找出单链表是否为循环/环形链表的算法？

Question

如何判断单向链表是否为环形的？我尝试过搜索但未找到令人满意的解决方案。如果可以的话，能否提供伪代码或Java实现呢？

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

- harshit

---

你搜索得有多努力？这个代码示例是C++语言的，但转换为Java语言将是轻而易举的。 - kgiannakakis

大多数实现中，列表不是循环的。它有第一个和最后一个元素，客户端不可以沿着两端走。内部用于实现列表的数据结构可能是循环列表（有一种方法可以识别回到头部）。这是两个不同抽象级别之间的重要区别。 - Steve Jessop

我不明白这个例子...它有什么循环之处？ - aberrant80

“circular”是什么意思？您是指它包含一个循环，还是它本身就是一个循环？ - Mark Byers

应该提供更多细节。您是否可以控制元素结构（例如，可以添加新字段）？您只需要检查纯粹的循环（即，最后一个元素指向头部），还是也需要检查循环子列表？ - Vlad H

Answer 1

标准答案是从开头取两个迭代器，将第一个迭代器向前移动一次，第二个迭代器向前移动两次。检查它们是否指向同一个对象。然后重复此操作，直到以两倍速增加的那个迭代器要么碰到第一个迭代器，要么到达末尾。

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

伪代码（非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;
      } 
   }
}

- Lou Franco

---

好处在于它可以检测到不一定从开头开始的循环，而“检查直到再次到达头部”只能检测完全循环的列表。 - Jon Skeet

这个算法被称为弗洛伊德循环查找算法，有时也被称为“乌龟兔子算法”。 - Bill the Lizard

在数学中，这个算法有时被用于循环查找，例如在分解大数时。因为搜索空间的形状类似于带有初始部分和末尾循环的希腊字母rho，所以它被称为rho算法（即Pollard's rho算法）。 - starblue

这是它的维基百科页面- http://en.wikipedia.org/wiki/Cycle_detection - RichardOD

一个单向链表只能有一个循环节点，而该算法可以找到它。您所讨论的是一些不唯一元素的向量，并且您想要找到最长跨度。您可以尝试搜索贪婪匹配算法来解决这个问题。 - Lou Franco

Answer 2

一种简单的算法叫做Floyd's算法，它使用两个指针a和b，它们都从链表的第一个元素开始。然后在每一步中，您将a增加一次，b增加两次。重复此过程，直到您到达列表的末尾（没有循环），或者a == b（链表包含一个循环）。

另一个算法是Brent's算法。

- Mark Byers

---

哦，我从未知道它还有另一个名字，除了龟兔赛跑。每天都有新的东西可学呢 :-D - Brent Writes Code

维基对Brent算法的描述并不是很清晰。如果目标是“加固”算法以防止循环行为，那么Brent算法的一个合理近似可以描述为“将第二个项目与第一个进行比较，将接下来的两个与第二个进行比较，将接下来的四个与第四个进行比较，将接下来的八个与第八个进行比较，以此类推”。这种方法的一个主要优点是，如果有一个迭代器应该产生所有不同的元素，但可能会错误地陷入循环，Brent算法将在不需要第二个迭代器的情况下工作。 - supercat

Answer 3

我知道的三种主要策略如下：

1. 从链表开始遍历，并跟踪您访问过的所有节点（例如，在映射中存储它们的地址）。每次访问新节点时，检查是否已经访问过它。如果已经访问了该节点，则显然存在循环。如果没有循环，最终将到达链表末尾。这并不是很好，因为需要O(N)的空间复杂度来存储额外信息。

2. Tortoise/Hare解法。在列表前面启动两个指针。第一个指针“乌龟”每次迭代向前移动一个节点。另一个指针“兔子”每次迭代向前移动两个节点。如果没有循环，兔子和乌龟都将到达链表末尾。如果存在循环，兔子将在某个时候超过乌龟，当发生这种情况时，您就知道存在循环。这是O(1)的空间复杂度和一个相当简单的算法。

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

- Brent Writes Code

---

3也是具有破坏性的，对于线程使用需要昂贵的O(n)写入（排他）锁定时间，而2只需要读取（非排他）锁定。 - R.. GitHub STOP HELPING ICE

Answer 4

如果你要计算节点数，并回到*头部。

- Batman

---

不，这样行不通。考虑 A->B->B 或 A->B->C->B。 - rlibby

@rlibby 这些是循环。对于“circular”，我只理解为一个循环，其中包括所有元素，因此尾->头。 - Dr. belisarius

@belisarius，是的，你说得对。我把它误读为循环，因为圆形没有太多意义：解决方案非常简单。我仍然认为这就是OP的意思。 - rlibby

@rlibby，所以我猜这个应该因为是最简单的一个而被点赞 :D - Dr. belisarius

Answer 5

以下是翻译的结果：

以下是一种可能的解决方法：

按照标准算法将链表按升序排序。 排序前：4-2-6-1-5 排序后：1-2-4-5-6

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

if(currentcode->data > currentnode->link->data) 即循环=真;

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

伙计们，我没有测试代码的设置。如果这个概念可行，请让我知道。

- newbie

---

你会如何对4-2-6-1-5-4进行排序？ - AaronHS

Answer 6

使用龟兔算法。

- leppie

---

如果您能自己解释而不仅仅给出名称并要求搜索，那将更有帮助。这不是这种答案的适当场所。 - TheLoneKing

这里没有人不会通过谷歌解决自己的疑问。但我相信这个网站存在的目的不仅仅是提供谷歌搜索建议。我认为在这里回答问题的正确方式是用言语解释答案。当然，您可以提供谷歌搜索建议和外部链接，以获取有关您在答案中解释的更多信息。 - TheLoneKing

去重是好的，但当它引入循环时就不好了。"Google brought me here"可能是一个例子，我们永远无法得到实际答案。也许我们可以使用龟兔算法来检测这种情况。 - kchoi

Answer 7

一个算法是：

1. 存储指向第一个节点的指针
2. 遍历列表，将每个节点指针与此指针进行比较
3. 如果遇到空指针，则不是循环链表
4. 如果在遍历时遇到第一个节点，则是循环链表

- Asha

---

假设列表循环回到第一个元素。如果列表是A->B->C->D->B...会怎样？ - Brent Writes Code

最后一个节点可以指向任何节点，不一定是第一个节点。 - ruslik

是的，我假设它连接到第一个节点。 - Asha

Answer 8

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

类似于：

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

由于动态数组的插入时间，这会稍微慢一些。

- samoz

---

如果圆以中心开始，那么这将失败。 - Vilx-

我们在谈论列表中的重复条目吗？ - akarnokd

samoz是正确的，考虑到问题特别询问循环链表，而不是循环。 - Bill the Lizard

根据最近的编辑，这个方法行不通，因为他确实在寻找循环。 - Thomas Owens

@Thomas 第二个算法应该解决那个条件。 - samoz

Answer 9

@samoz 在我看来给出了答案！伪代码缺失。应该是这样的：

yourlist 是你的链表

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

抱歉，代码非常伪代码（最近更多地进行脚本编写而不是Java）

- leo

---

基本上，new HashSet(llist).size() <> llist.size()？ - akarnokd

不，我认为这可能会导致无限循环，并在一段时间后崩溃。你真的必须对其进行迭代。 - leo

好的。看起来，循环性是由列表值本身定义的，而不是列表中的下一个指针。 - akarnokd

Answer 10

这是一个不错的网站，可以复制不同的解决方案。

查找单链表中的循环

这是该网站上的获胜者。

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

这个解决方案是1967年罗伯特·W·弗洛伊德在《非确定性算法》中发表的“弗洛伊德循环查找算法”。它也被称为“乌龟和兔子算法”。

- Markus Lausberg