Detect a Cycle (Floyd's Tortoise and Hare)

time: O(n)
space: O(1)
tags: linked-lists · two-pointer · cycle-detection

in the wild Detect an infinite loop in a state-machine transition graph; spot a follow-cycle in social graphs.

Problem

Given the head of a linked list, determine whether the list contains a cycle. A cycle exists if some node's next pointer eventually leads back to a previously visited node.

Return true if there's a cycle; false otherwise.

Examples

1 → 2 → 3 → 4 → 2 → ... (where the last 4 points back to 2) → true
1 → 2 → 3 → ∅ → false
1 → 1 → 1 → ... (self-loop) → true
∅ → false

Why this is the canonical two-pointer-on-pointers problem

Naïve solution: use a hash set to remember every node pointer you've visited. If you ever revisit one, there's a cycle. That's O(n) time but O(n) space.

Floyd's tortoise-and-hare trick gets it to O(n) time with O(1) space. Two pointers walk the list at different speeds:

Slow advances one node per step (the tortoise).
Fast advances two nodes per step (the hare).

If there's no cycle, fast hits null and we return false. If there's a cycle, fast eventually catches slow inside the loop — like two runners on a circular track at different speeds, they must lap each other.

The number-theoretic argument: once both pointers enter the cycle of length L, each step closes the gap between them by 1. So in at most L steps after both are in the cycle, they meet.

Hints

Hint 1 — what cycles look like

A cycle means there's a node n such that following next pointers from the head eventually arrives back at n without ever hitting null. Equivalently: there exist two distinct positions in the traversal that share the same node reference.

Hint 2 — use two pointers at different speeds

If two pointers traverse the list at different speeds, what happens if there's a cycle? What happens if there isn't?

(There's no cycle → the faster one hits null. There's a cycle → they end up on the same node eventually.)

Hint 3 — pseudocode

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True
return False

Edge case: if fast or fast.next is None, we walked off the end → no cycle.

Solution

class Node:
    def __init__(self, val: int, nxt: "Node | None" = None):
        self.val, self.next = val, nxt

def has_cycle(head: Node | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next        # advance by 1
        fast = fast.next.next   # advance by 2
        if slow is fast:        # pointer-equality, not value-equality
            return True
    return False                # fast walked off → no cycle

# Build a list and (optionally) stitch a cycle back to a node by index.
def build(values, cycle_at=-1):
    if not values: return None
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1): nodes[i].next = nodes[i + 1]
    if cycle_at >= 0: nodes[-1].next = nodes[cycle_at]
    return nodes[0]

cases = [
    ([1, 2, 3, 4],      -1, False),  # no cycle
    ([1, 2, 3, 4],       1, True),   # cycle back to index 1
    ([1],                0, True),   # self-loop
    ([1, 2, 3],         -1, False),
    ([],                -1, False),
]
for vs, cy, expected in cases:
    got = has_cycle(build(vs, cy))
    mark = "✓" if got == expected else "✗"
    print(f"{mark} has_cycle({vs}, cycle_at={cy}) = {got}")

class Node {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;   // reference-equality
  }
  return false;
}

function build(values, cycleAt = -1) {
  if (!values.length) return null;
  const nodes = values.map((v) => new Node(v));
  for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i + 1];
  if (cycleAt >= 0) nodes[nodes.length - 1].next = nodes[cycleAt];
  return nodes[0];
}

const cases = [
  [[1, 2, 3, 4], -1, false],
  [[1, 2, 3, 4],  1, true],
  [[1],           0, true],
  [[1, 2, 3],    -1, false],
  [[],           -1, false],
];
for (const [vs, cy, expected] of cases) {
  const got = hasCycle(build(vs, cy));
  console.log(`${got === expected ? "✓" : "✗"} hasCycle(${JSON.stringify(vs)}, cycle_at=${cy}) = ${got}`);
}

// Safe Rust can't build a cyclic Box<Node> — ownership is a tree, not
// a graph. The canonical fix is Rc<RefCell<Node>> for shared/interior-
// mutable references. We compare nodes with Rc::ptr_eq.

use std::cell::RefCell;
use std::rc::Rc;

type Link = Option<Rc<RefCell<Node>>>;

pub struct Node { pub val: i32, pub next: Link }

pub fn has_cycle(head: Link) -> bool {
    let mut slow = head.clone();
    let mut fast = head;
    while let (Some(s), Some(f)) = (slow.clone(), fast.clone()) {
        let f_next = f.borrow().next.clone();
        let Some(fn1) = f_next else { return false; };
        slow = s.borrow().next.clone();
        fast = fn1.borrow().next.clone();
        if let (Some(s2), Some(f2)) = (slow.clone(), fast.clone()) {
            if Rc::ptr_eq(&s2, &f2) { return true; }
        }
    }
    false
}

fn build(values: &[i32], cycle_at: i32) -> Link {
    if values.is_empty() { return None; }
    let nodes: Vec<_> = values.iter()
        .map(|&v| Rc::new(RefCell::new(Node { val: v, next: None })))
        .collect();
    for i in 0..nodes.len() - 1 {
        nodes[i].borrow_mut().next = Some(nodes[i + 1].clone());
    }
    if cycle_at >= 0 {
        nodes.last().unwrap().borrow_mut().next = Some(nodes[cycle_at as usize].clone());
    }
    Some(nodes[0].clone())
}

fn main() {
    let cases: &[(&[i32], i32, bool)] = &[
        (&[1, 2, 3, 4], -1, false),
        (&[1, 2, 3, 4],  1, true),
        (&[1],            0, true),
        (&[1, 2, 3],    -1, false),
        (&[],           -1, false),
    ];
    for (vs, cy, expected) in cases {
        let got = has_cycle(build(vs, *cy));
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} has_cycle({:?}, cycle_at={}) = {}", vs, cy, got);
    }
}

#include <iostream>
#include <vector>

struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} };

bool has_cycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// Build with raw pointers; leaks on cycle (we don't free in the demo).
Node* build(const std::vector<int>& vs, int cycle_at) {
    if (vs.empty()) return nullptr;
    std::vector<Node*> nodes;
    for (int v : vs) nodes.push_back(new Node(v));
    for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1];
    if (cycle_at >= 0) nodes.back()->next = nodes[cycle_at];
    return nodes[0];
}

int main() {
    struct Case { std::vector<int> vs; int cy; bool expected; };
    std::vector<Case> cases = {
        {{1,2,3,4}, -1, false}, {{1,2,3,4}, 1, true},
        {{1}, 0, true}, {{1,2,3}, -1, false}, {{}, -1, false},
    };
    for (auto& c : cases) {
        bool got = has_cycle(build(c.vs, c.cy));
        std::cout << (got == c.expected ? "✓" : "✗")
                  << " has_cycle(.., cycle_at=" << c.cy << ") = "
                  << (got ? "true" : "false") << "\n";
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node { int val; struct Node* next; } Node;

bool has_cycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Node* build(const int* vs, int n, int cycle_at) {
    if (n == 0) return NULL;
    Node** nodes = malloc(n * sizeof(Node*));
    for (int i = 0; i < n; i++) {
        nodes[i] = malloc(sizeof(Node));
        nodes[i]->val = vs[i]; nodes[i]->next = NULL;
    }
    for (int i = 0; i < n - 1; i++) nodes[i]->next = nodes[i + 1];
    if (cycle_at >= 0) nodes[n - 1]->next = nodes[cycle_at];
    Node* head = nodes[0];
    free(nodes);  // we just freed the lookup table, list nodes are still alive
    return head;
}

int main(void) {
    struct { int vs[4]; int n; int cy; bool expected; } cases[] = {
        {{1,2,3,4}, 4, -1, false},
        {{1,2,3,4}, 4,  1, true},
        {{1},       1,  0, true},
        {{1,2,3},   3, -1, false},
        {{0},       0, -1, false},
    };
    for (int i = 0; i < 5; i++) {
        bool got = has_cycle(build(cases[i].vs, cases[i].n, cases[i].cy));
        printf("%s has_cycle(.., cycle_at=%d) = %s\n",
               got == cases[i].expected ? "✓" : "✗",
               cases[i].cy, got ? "true" : "false");
    }
    return 0;
}

idle

Notice how Python and JS are nearly identical — both have GC and reference-equality. C++ uses raw pointers (we accept the leak in this demo since cyclic structures can't be cleanly freed). C is the same as C++ minus the standard library. Rust's safe variant needs Rc<RefCell<...>> because owned Box<T> can't form a cycle by design — Rust prevents memory leaks at compile time, but the price is more ceremony when you genuinely want shared ownership.

Complexity

Time: O(n) — if no cycle, fast walks the list once (n/2 steps). With cycle of length L, slow + fast meet in at most n + L iterations.
Space: O(1) — two pointers, no auxiliary data.
vs hash-set approach: Hash version: O(n) time, O(n) space. Floyd's: O(n) time, O(1) space — strictly better.

In the wild

State machines. Detecting an unreachable / looping state in a transition graph by treating it as a "linked list" of successor states.
Graph cycle detection. The same tortoise/hare logic generalizes to directed graphs — though for general graphs DFS-based detection (back-edge check) is more common.
Detecting infinite recursion at runtime. Some debuggers run a periodic check that compares the call-stack pointer at time t and 2t.
Iterator de-duplication. If you suspect a generator is looping back to a previous value, run two iterators at different speeds.

Variations

Find the entry node of the cycle. Once slow and fast meet, reset slow to head. Walk both at speed 1; they meet at the cycle's entry point. (Number theory trick: distance from head to cycle entry equals distance from meet-point to cycle entry going forward.)
Find the cycle's length. Once they meet inside, keep fast still and walk slow until it returns to fast — that's the length.
Happy number problem. Same algorithm applied to a sequence of integers; "next" is the digit-square-sum operation.