查找单链表是否为循环/循环的有效算法是什么？

Question

如何查找单链表是循环/循环还是循环？我试图搜索但找不到满意的解决方案.如果可能,您能提供伪代码或Java实现吗？

例如:
1→交通3→交通5→交通71→交通45→交通7→交通5,其中第二个5实际上是列表的第三个元素.

Answer 1

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

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

伪代码(不是J​​ava,未经测试 - 脱离我的头脑)

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

Answer 2

一个名为Floyd算法的简单算法是有两个指针a和b,它们都从链表中的第一个元素开始.然后在每一步增加一次和两次b.重复直到你到达列表的末尾(没有循环),或者a == b(链表包含循环).

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

Answer 3

我所知道的三个主要策略:

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

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

3. 使用该算法可以反转链接列表.如果列表有一个循环,那么在尝试反转它时,你最终会回到列表的开头.如果它没有循环,你将完成倒转并结束.这是O(1)空间复杂度,但是稍微丑陋的算法.