查找单链表是循环还是循环是一种有效的算法？ [英] What is an efficient algorithm to find whether a singly linked list is circular/cyclic or not?

问题描述

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

How can I find whether a singly linked list is circular/cyclic or not? I tried to search but couldn't find a satisfactory solution. If possible, can you provide a pseudo-code or Java-implementation?

例如：

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

For instance:
1 → 3 → 5 → 71 → 45 → 7 → 5, where the second 5 is actually the third element of the list.

推荐答案

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

The standard answer is to take two iterators at the beginning, increment the first one once, and the second one twice. Check to see if they point to the same object. Then repeat until the one that is incrementing twice either hits the first one or reaches the end.

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

This algorithm finds any circular link in the list, not just that it's a complete circle.

伪代码（不是J​​ava，未经测试 - 从我的头顶部）

Pseudo-code (not Java, untested -- off the top of my head)

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

这篇关于查找单链表是循环还是循环是一种有效的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！