什么是有效的算法来找到一个单向链表是否是圆形/循环与否？ [英] What is an efficient algorithm to find whether a singly linked list is circular/cyclic or not?

问题描述

我怎样才能找到一个单向链表是否是圆形/循环与否？我试图寻找，但没有找到一个满意的解决方案。如果可能的话，你可以提供的伪code或Java？

How can i find whether a singly linked list is circular/cyclic or not? I Tried searching but couldn't find a satisfactory solution. If possible, can you provide pseudocode or Java?

例如 1 3 5 71 45 7 5 - 停止，它是一个循环链表

For Example 1 3 5 71 45 7 5 -stop , its a circular linked 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.

伪code（不是Java，未经检验的 - 我的头顶部）

Pseudo-code (not Java, untested -- of 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屋！