algorithm - 如何确定链表是否具有仅使用两个内存位置的循环

Question

有谁知道一种算法可以仅使用两个变量来遍历列表来查找链表是否自循环。假设您有一个对象链表，对象的类型无关紧要。我在一个变量中有一个指向链表头部的指针，我只得到另一个变量来遍历列表。

所以我的计划是比较指针值，看看是否有相同的指针。该列表的大小有限，但可能很大。我可以将两个变量都设置为头部，然后用另一个变量遍历列表，始终检查它是否等于另一个变量，但是，如果我确实遇到了循环，我将永远无法摆脱它。我认为这与遍历列表和比较指针值的不同速率有关。有什么想法吗？

Answer 1

我建议使用 Floyd 的循环查找算法 又名龟兔赛跑算法。它具有 O(n) 复杂度，我认为它符合您的要求。

示例代码:

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

有关维基百科的更多信息:Floyd's cycle-finding algorithm .