Algo: Floyd Cycle Detection Algorithm

Detecting cycles in sequences—whether in linked lists, function outputs, or state machines—is a fundamental problem in computer science and engineering. Floyd's tortoise-and-hare algorithm provides an elegant solution that operates in $O(n)$ time using only $O(1)$ auxiliary space, making it vastly more efficient than naive approaches that require extra memory. Mastering this technique not only sharpens your algorithmic thinking but also equips you to solve a wide range of problems from debugging infinite loops to analyzing pseudorandom number generators.

The Tortoise and Hare: Core Intuition

The algorithm, often called the tortoise-and-hare algorithm, employs two pointers that traverse a sequence at different speeds. Imagine a race where a tortoise (slow pointer) moves one step at a time, while a hare (fast pointer) moves two steps. If the sequence has no cycle, the hare will eventually reach the end. However, if a cycle exists, the hare will lap the tortoise inside the cycle, causing them to meet. This meeting point proves a cycle is present. The beauty lies in its constant-space requirement; unlike methods using hash tables, it only needs two pointers regardless of sequence length, achieving $O(1)$ space complexity. The time complexity is $O(n)$ because, in the worst case, both pointers traverse the linear portion and cycle a finite number of times before meeting.

This analogy translates directly to code. For a linked list, you initialize two pointers, tortoise and hare, at the head. In each iteration, you move tortoise by one node and hare by two nodes. If hare or hare.next becomes null, no cycle exists. If tortoise == hare at any point, a cycle is detected. The logic hinges on the relative speeds: the hare gains one step per iteration on the tortoise within a cycle, guaranteeing a meeting if a cycle is present.

Implementing Cycle Detection in Linked Lists

Let's walk through a concrete implementation for a singly linked list, the most common scenario. Assume a node structure with a value and a next pointer. You start both pointers at the head node. The critical check is ensuring the hare's moves are safe; before advancing two steps, you must verify that hare and hare.next are not null to avoid null pointer errors.

Here is a step-by-step breakdown in pseudocode:

function hasCycle(head):
    if head is null: return false
    tortoise = head
    hare = head
    while hare is not null and hare.next is not null:
        tortoise = tortoise.next
        hare = hare.next.next
        if tortoise == hare:
            return true
    return false

In this loop, the hare moves twice as fast. The condition tortoise == hare checks for pointer equality, meaning they reference the same node object. This detection phase runs in linear time because, even with a cycle, the hare will meet the tortoise within a number of iterations proportional to the total number of nodes. For a list with $n$ nodes, the maximum steps before meeting is $O(n)$, as the hare traverses at most $2n$ steps.

Finding the Cycle Start and Length

Once a cycle is detected, you can extend the algorithm to find the starting node of the cycle and its length. This is where modular arithmetic comes into play. After the tortoise and hare meet, reset one pointer to the head of the list while keeping the other at the meeting point. Then, move both pointers one step at a time; they will meet again at the cycle's starting node.

The reasoning involves distances. Let $L$ be the distance from the head to the cycle start, $C$ be the cycle length, and $K$ be the distance from the cycle start to the meeting point. When they meet, the tortoise has traveled $L+K$ steps, and the hare has traveled $L+K+mC$ steps (where $m$ is an integer representing extra laps). Since the hare moves twice as fast, we have $2(L+K)=L+K+mC$, which simplifies to $L=mC-K$. This means the distance from head to cycle start equals an integer multiple of $C$ minus $K$. Therefore, moving from the head and meeting point at the same pace will align at the start after $L$ steps.

To find the cycle length, keep one pointer fixed at the meeting point and move the other one step at a time within the cycle until it returns to the meeting point, counting the steps. This count is $C$, the cycle length. Both operations maintain $O(n)$ time and $O(1)$ space.

Applications to Function Iteration Problems

The algorithm isn't limited to linked lists; it applies to any sequence generated by function iteration. Consider a function $f(x)$ that maps a finite set to itself, like in pseudorandom number generators or detecting cycles in mathematical sequences (e.g., the Collatz conjecture). Here, the sequence is $x_0,f(x_0),f(f(x_0)),\dots$. You can model this with two "pointers" to sequence values, advancing one by one application of $f$ and the other by two applications.

For example, to detect if iterating $f$ from an initial value leads to a cycle, initialize tortoise = f(x0) and hare = f(f(x0)). Then, in a loop, update tortoise = f(tortoise) and hare = f(f(hare)). If they become equal, a cycle exists. This is useful in cryptography for analyzing periodicity or in debugging recursive functions. The space efficiency remains $O(1)$ since you only store two states, and time is $O(\mu +\lambda )$, where $\mu$ is the distance to cycle and $\lambda$ is cycle length, which is linear in total steps.

Proving Correctness with Modular Arithmetic

A rigorous proof solidifies your understanding. Let the sequence indices be $0,1,2,\dots$ in a cycle of length $C$ starting at index $\mu$. After $\mu$ steps, the sequence enters the cycle. Let $x_i$ denote the element at index $i$. The tortoise position at step $t$ is $x_t$, and the hare is $x_{2t}$. For detection, we need to show that if a cycle exists, there exists a $t$ such that $x_t=x_{2t}$.

Once in the cycle, indices are modulo $C$. Suppose the tortoise enters the cycle at step $\mu$, so for $t\ge \mu$, $x_t=x_{\mu +((t-\mu )\mathrm{mod}C)}$. The hare enters at step $2\mu$. The meeting condition $x_t=x_{2t}$ reduces to $\mu +((t-\mu )\mathrm{mod}C)=\mu +((2t-\mu )\mathrm{mod}C)$ modulo the cycle. This simplifies to $(t-\mu )\equiv (2t-\mu )(\mathrm{mod}C)$, or $t\equiv 2t(\mathrm{mod}C)$, meaning $t\equiv 0(\mathrm{mod}C)$. Thus, they meet when $t$ is a multiple of $C$ after entering the cycle, which must happen within $O(n)$ steps. This modular argument also underpins the method for finding the cycle start, as derived earlier.

Common Pitfalls

When implementing Floyd's algorithm, several mistakes can lead to incorrect results or infinite loops.

1. Incorrect pointer advancement for the hare: Always check that hare and hare.next are not null before accessing hare.next.next. Failing to do so causes null pointer dereferences in non-cyclic lists. For function iteration, ensure the function handles all inputs to avoid errors.

1. Misidentifying the cycle start: After detection, resetting the wrong pointer can fail to find the start. Remember to move one pointer to the head and advance both one step at a time. Confusing this with continuing at different speeds is a frequent error.

1. Assuming meeting implies cycle start: The meeting point inside the cycle is not necessarily the cycle's starting node. You must use the second phase to find the start. Students often stop after detection and incorrectly report the meeting node as the start.

1. Overlooking edge cases: For linked lists, handle empty lists (head is null) or single-node cycles properly. In function iteration, consider cases where the function might not be defined for some values, requiring domain checks.

Summary

• Floyd's tortoise-and-hare algorithm detects cycles using two pointers moving at different speeds, achieving $O(n)$ time and $O(1)$ space, making it memory-efficient for sequences.
• The method extends beyond linked lists to find the cycle's starting point and length by leveraging modular arithmetic and a second pointer reset phase.
• Applications include function iteration problems in mathematics and computer science, such as analyzing recursive functions or pseudorandom sequences.
• Proof of correctness relies on distance equations and modular reasoning, ensuring the pointers meet within linear time if a cycle exists.
• Avoid common pitfalls like unsafe pointer moves and missteps in locating the cycle start by following the algorithm's phases precisely.
• Mastering this algorithm enhances your ability to solve cycle-related problems in interviews, debugging, and algorithmic design with optimal resource usage.