Skip to main content

Tortoise & Hare

Premium

The tortoise & hare is a technique used to detect cycles in linked lists or sequences. It’s a two-pointer approach where one pointer (the "tortoise") moves one step at a time while the other pointer (the "hare") moves two steps. If there is a cycle, the hare will eventually meet the tortoise.

When to use it

You can identify problems that can be solved using the tortoise and hare technique if they meet one or more of these conditions:

  1. The problem involves a linked list or a sequence.
  2. You're tasked with determining if a cycle exists in the structure.
  3. The solution needs to run in constant space (O(1)O(1) space complexity).

Why use it

Tortoise & Hare provides an efficient way to detect cycles with minimal space usage. It operates with O(n) time complexity but only requires O(1)O(1) space, which makes it ideal for situations where memory consumption is a concern, such as working with large linked lists.

How it works

The idea is to have two pointers starting from the head of the list or sequence. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If the fast pointer ever "catches up" to the slow pointer, it means there’s a cycle.

For example, consider a linked list where some nodes may form a cycle. If the slow and fast pointers meet, you know there’s a cycle. If the fast pointer reaches the end (null), the list has no cycle.

Python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Tortoise and hare

Examples

  1. Finding the length of a cycle in a linked list
    • Problem: After detecting a cycle in a linked list, determine its length.
    • Approach: Once the slow and fast pointer meet, keep one pointer fixed and move the other around the cycle until it returns to the same point, counting the steps.
Next Lesson