什么是确定单链表是否为循环/循环的有效算法? [英] 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.

伪代码(不是 Java，未经测试 - 在我的脑海中)

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屋！