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.

It's called "tortoise & hare" because tortoises are slow and hares are fast.

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

Not just for cycle detection: The tortoise & hare technique can also be used to solve other problems involving linked lists, such as finding the middle of a list. You can set a slow and fast pointer such that when the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Python
def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow will be at the middle

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