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

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

alisabaj profile image Alisa Bajramovic Updated on ・4 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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

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.

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!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

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!