Introduction

The standard answer to linked-list cycle detection is Floyd's Tortoise and Hare algorithm. It is widely considered the best general-purpose approach because it runs in linear time, uses constant extra space, and does not modify the list.

Why Floyd's Algorithm Works

The algorithm uses two pointers:

• 'slow, which moves one node at a time'
• 'fast, which moves two nodes at a time'

If the list has no cycle, fast eventually reaches the end and the algorithm stops. If the list does have a cycle, fast eventually laps slow inside the loop and both pointers point to the same node.

That meeting point is the proof that a cycle exists.

Basic Implementation

Here is a straightforward Python version:

1class Node:
2    def __init__(self, value):
3        self.value = value
4        self.next = None
5
6
7def has_cycle(head):
8    slow = head
9    fast = head
10
11    while fast is not None and fast.next is not None:
12        slow = slow.next
13        fast = fast.next.next
14
15        if slow is fast:
16            return True
17
18    return False

This runs in O(n) time because each pointer traverses the list at most a linear number of steps. It uses O(1) extra space because only a few references are stored.

Example With a Cycle

1a = Node("A")
2b = Node("B")
3c = Node("C")
4d = Node("D")
5
6a.next = b
7b.next = c
8c.next = d
9d.next = b
10
11print(has_cycle(a))

Output:

True

The node D points back to B, so the list never ends. The fast pointer eventually catches the slow pointer inside that loop.

Finding the Start of the Cycle

One reason Floyd's algorithm is especially useful is that it can do more than answer yes or no. After slow and fast meet, reset one pointer to the head and move both one step at a time. The node where they meet next is the start of the cycle.

1def find_cycle_start(head):
2    slow = head
3    fast = head
4
5    while fast is not None and fast.next is not None:
6        slow = slow.next
7        fast = fast.next.next
8
9        if slow is fast:
10            break
11    else:
12        return None
13
14    slow = head
15    while slow is not fast:
16        slow = slow.next
17        fast = fast.next
18
19    return slow

This extra step keeps the same asymptotic performance and is often useful in debugging corrupted pointer structures.

Why Not Use a Hash Set

Another valid solution is to store each visited node in a hash set and stop if you see one twice.

1def has_cycle_with_set(head):
2    seen = set()
3    current = head
4
5    while current is not None:
6        if id(current) in seen:
7            return True
8        seen.add(id(current))
9        current = current.next
10
11    return False

This is still linear time on average, but it uses extra memory proportional to the number of visited nodes. That is why Floyd's method is usually preferred unless clarity matters more than space.

Common Pitfalls

The most common bug is advancing fast without checking that both fast and fast.next are not None. That causes crashes on short or acyclic lists.

Another pitfall is comparing node values instead of node identities. Two different nodes can hold the same value, so the test must check whether the pointers refer to the same node object.

Developers also sometimes modify the list while traversing it, for example by marking nodes. That can work in controlled environments, but it changes the data structure and is rarely necessary.

Finally, do not assume a cycle always starts at the head. Floyd's algorithm detects cycles anywhere in the reachable list and can locate the true entry point afterward.

Summary

• Floyd's Tortoise and Hare algorithm is the standard choice for cycle detection in linked lists.
• It runs in O(n) time and O(1) extra space.
• If the fast and slow pointers meet, the list contains a cycle.
• The same technique can also find the cycle's entry node.
• Hash-set solutions are simpler to explain but use more memory.