Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List
Tags: algorithms, javascript, codenewbie, linkedlist
Published: 2020-05-27 15:19:58

Today's [algorithm](https://leetcode.com/problems/linked-list-cycle/) is about cycles in a linked list:
>Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

For example, if the input were given that `head = [1, 3, 2, 5]` and `pos = 1`, the linked list would look like this:

![Linked list with a cycle. The linked list is [1, 3, 2, 5], and after 5, the arrow points back to 3, forming a cycle.](https://dev-to-uploads.s3.amazonaws.com/i/adu3dg4kdnkcakun5j9p.png)


This problem can be solved in a couple of different ways. One of which is to have a hash or set, keeping track of every node seen. If a node has already been seen, then you know it's a cycle.

I came across [Floyd's Cycle Detection Algorithm](https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare), also known as Floyd's Tortoise and Hare Algorithm. The idea behind the algorithm is that, if you have two pointers in a linked list, one moving twice as fast (the hare) than the other (the tortoise), then if they intersect, there is a cycle in the linked list. If they don't intersect, then there is no cycle.

In this post, I'll explain the solution to this problem, then I'll use an example to illustrate why it works.

## Finding a Cycle With the Tortoise and Hare

In the problem, you're asked to return a boolean for whether or not there is a cycle. You're given the head of the linked list, and each node has a value (`.val`) and the next node can be found with `.next`.

The first thing I'll do is check if `head` exists, and if `head.next` exists. If neither exist, then there is no cycle, and I'll immediately return false.

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

Next, I'll initiate a slow and fast pointer. The slow pointer, `tortoise`, will start at the head node. The fast pointer, `hare`, will start one step ahead, at head.next.

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

  //...
}
```

Now, as long as the hare is still pointing at a node that isn't null, and the next node still isn't null, we will continue checking things. Therefore, this is a good place to have a while loop.

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

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

Inside the while loop, the first thing to do is to check if the tortoise and hare are pointing to the same node. If they are, that means it's a cycle, so we can return `true`.

```javascript
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;
    }
    //...
  }
  //...
}
```

Otherwise, we will move the tortoise and hare. The tortoise moves one node at a time, and the hare moves two nodes at a time.

```javascript
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;
  }
  //...
}
```
Finally, if the while loop cannot continue because `hare` and/or `hare.next` is null, then that means no cycle was ever found, so we can return `false`.

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

## Showing How This Works

To help illustrate this algorithm, I'll use some very relevant clipart. We'll start with the linked list. The tortoise begins at the head, while the hare begins at head.next.

![Linked list with a cycle. Linked list is [1, 3, 2, 5], and after 5 the arrow points back to 3. Clipart of a tortoise on the first node, 1, and a hare on the second node, 3.](https://dev-to-uploads.s3.amazonaws.com/i/chpcvc0wjmpx2mi3l5l9.png)


Since hare and hare.next are both not null, we'll enter the while loop. Tortoise and hare are not equal to each other, so we will move them both over. Tortoise gets moved over one spot, and hare gets moved over two spots.

![The tortoise and hare have moved. Hare is at the second node, 3, and tortoise is at the fourth node, 5.](https://dev-to-uploads.s3.amazonaws.com/i/pwel97dag1dw06w37krn.png)


The while loop is still true. Again, tortoise and hare are not equal to each other. We'll move the tortoise over one, and the hare over two nodes.

![The tortoise and hare have moved. Hare is at the third node, 2, and tortoise as at the same node.](https://dev-to-uploads.s3.amazonaws.com/i/fe5sgzzti21d5nf6vumt.png)

The while loop is still true, but this time, tortoise and hare are equal to each other. This means that a cycle was found, so we will return true.

--

Feel free to leave me any questions or alternate approaches in the comments!