DEV Community

Cover image for Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List
Alisa Bajramovic
Alisa Bajramovic

Posted on • Updated on

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:

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.

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
  }
  //...
}


Enter fullscreen mode Exit fullscreen mode

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;

  //...
}


Enter fullscreen mode Exit fullscreen mode

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) {
    //...
  }
  //...
}


Enter fullscreen mode Exit fullscreen mode

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


Enter fullscreen mode Exit fullscreen mode

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


Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode




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.

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.

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.

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!

Top comments (8)

Collapse
 
lilyyanglt profile image
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!

Collapse
 
rajeshs_sem profile image
Rajesh Subramanian

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

Collapse
 
mayurghule profile image
Mayur Ghule

Thank You Alisa , It's a great explanation.

Collapse
 
noto1998 profile image
Sangram

It will meet on 3 rd recursion.

Collapse
 
ambush3 profile image
Ambush3

Amazing post! Thank you for this!

Collapse
 
sahajicodes profile image
Manish Sahu

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

Collapse
 
andrewbumetsov profile image
Andrew Polukhin

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

Collapse
 
fjch1997 profile image
Jingchao Feng

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