Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List

Today's algorithm 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:

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, 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.

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.

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.

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.

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.

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.

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.

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 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 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!

Comments

[Mayur Ghule]

Thank You Alisa , It's a great explanation.

[Sangram]

It will meet on 3 rd recursion.

[Ambush3]

Amazing post! Thank you for this!

[Jingchao Feng]

Can you please explain why this algorithm is correct on any graph?

[Andrew Polukhin]

The design is just awesome! Liked the pictures, very appealing and easy to read :)

[Manish Sahu]

I feel that, we should firstly move tortoise and hare, before comparing that they are equal or not....

[Rajesh Subramanian]

It is a good explanation with simple terms of Floyd's Cycle detection algorithm. Greak work!.

[Lily]

Thank you for this!! I was working on a problem on leetcode and came across a mention of the floyd cycle detection algorithm. It's so hard to understand on wikipedia, but your article helps clarify with the cute arts! Thank you so much!