弗洛伊德龟兔算法：寻找链表中的循环

今天的算法是关于链表中的循环：

给定一个链表，判断其中是否存在循环。为了表示给定链表中的循环，我们使用一个整数 pos，它表示链表中 tail 所连接的位置（从 0 开始）。如果 pos 为 -1，则表示链表中不存在循环。

例如，如果输入为head = [1, 3, 2, 5]和pos = 1，则链表将如下所示：

这个问题可以用几种不同的方法解决。其中一种方法是使用一个哈希或集合来跟踪每个看到的节点。如果一个节点已经被看到，那么你就知道它是一个环。

我偶然发现了弗洛伊德循环检测算法，又称弗洛伊德龟兔算法。该算法背后的原理是：如果一个链表中有两个指针，其中一个指针（兔子）的移动速度是另一个指针（乌龟）的两倍，如果它们相交，则链表中存在循环。如果它们不相交，则不存在循环。

在这篇文章中，我将解释这个问题的解决方案，然后用一个例子来说明它为什么有效。

龟兔赛跑，寻找循环

题目要求你返回一个布尔值来判断是否存在循环。给定一个链表的头节点，每个节点都有一个值（.val），下一个节点可以通过找到.next。

我首先会检查是否head存在head.next。如果都不存在，则说明不存在循环，并立即返回 false。

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  //...
}

接下来，我将启动一个慢速指针和一个快速指针。慢速指针tortoise将从头节点开始。快速指针hare将从 head.next 开始，向前一步。

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  //...
}

现在，只要兔子仍然指向一个非空节点，并且下一个节点仍然不为空，我们就会继续检查。因此，这里很适合使用 while 循环。

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    //...
  }
  //...
}

在 while 循环中，首先要检查乌龟和兔子是否指向同一个节点。如果是，则说明这是一个循环，因此我们可以 return true。

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    //...
  }
  //...
}

否则，我们就移动乌龟和兔子。乌龟每次移动一个节点，兔子每次移动两个节点。

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    tortoise = tortoise.next;
    hare = hare.next.next;
  }
  //...
}

最后，如果 while 循环由于hareand/orhare.next为空而无法继续，则意味着没有找到循环，因此我们可以返回false。

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    tortoise = tortoise.next;
    hare = hare.next.next;
  }
  return false;
}

演示其工作原理

为了帮助说明这个算法，我将使用一些非常相关的剪贴画。我们从链表开始。乌龟从 head 开始，而兔子从 head.next 开始。

由于 hare 和 hare.next 都不为空，我们将进入 while 循环。Tortoise 和 hare 彼此不相等，因此我们将它们都移动。Tortoise 移动一个位置，而 hare 移动两个位置。

while 循环仍然成立。同样，乌龟和兔子并不相等。我们将乌龟移动到一个节点，兔子移动到两个节点。

while 循环仍然为真，但这次，乌龟和兔子相等。这意味着发现了一个循环，因此我们返回 true。

请随时在评论中给我留下任何问题或其他方法！

文章来源：https://dev.to/a_b_102931/floyd-s-tortoise-and-hare-algorithm-finding-a-cycle-in-a-linked-list-39af