Linked List Cycle: Floyd's Tortoise and Hare

April 30, 20266 min read

leetcodeproblemeasylinked-list

Linked List Cycle is LeetCode problem 141. It is one of those problems that looks simple on the surface, but the optimal solution relies on an algorithm that feels like magic the first time you see it.

The brute force approach (use a hash set to track visited nodes) works fine, but it costs O(n) space. Floyd's algorithm, also known as the tortoise and hare technique, solves it in O(1) space. That is the version interviewers want to see, and it is the version you should know cold.

The problem

You are given the head of a linked list. Determine if the list has a cycle in it. A cycle exists when some node's next pointer points back to an earlier node, so following next pointers would loop forever.

Return true if there is a cycle, false otherwise.

The tail node (-4) points back to node 2, creating a cycle. A naive traversal would loop forever.

Why not just use a set?

The straightforward approach is to walk through the list and add each node to a hash set. If you ever visit a node that is already in the set, you found a cycle. If you reach null, the list is cycle-free.

def hasCycle(head):
    seen = set()
    curr = head
    while curr:
        if curr in seen:
            return True
        seen.add(curr)
        curr = curr.next
    return False

This works. It is correct. But it uses O(n) extra space for the set. Interviewers will follow up: "Can you do it in O(1) space?" That is where Floyd's algorithm comes in.

Practice this pattern

Floyd's algorithm: the tortoise and hare

The idea is beautifully simple. Use two pointers:

slow moves one step at a time
fast moves two steps at a time

Both start at the head. If there is no cycle, fast will reach null and you are done. If there is a cycle, fast will eventually lap slow and they will land on the same node. That is your proof that a cycle exists.

Think of it like two runners on a circular track. The faster runner will always catch the slower one. They are not running toward each other. The fast runner simply closes the gap by one node every step until the gap reaches zero.

Visual walkthrough

Let's trace through the list 3 -> 2 -> 0 -> -4 -> (back to 2). Watch slow (amber) and fast (green) as they move through the cycle.

Start: Both pointers at the head

slow moves 1 step per turn. fast moves 2 steps per turn.

Step 1: slow moves to 2, fast moves to 0

slow = node 2. fast = node 0. They have not met yet.

Step 2: slow moves to 0, fast wraps around to 2

fast hit -4 and followed the cycle arrow back to 2. Still no match.

Step 3: slow moves to -4, fast moves to -4. They meet!

Both pointers are at node -4. Cycle detected! Return true.

It took just 3 steps. Fast entered the cycle first, slow followed, and then fast caught up to slow from behind. Once they collide, we know there is a cycle and return true.

Why does fast always catch slow?

This is the part that trips people up. Why is it guaranteed that fast catches slow? Why can't fast keep jumping over slow forever?

Here is the key insight. Once both pointers are inside the cycle, think about the gap between them. Each step, slow moves forward 1, and fast moves forward 2. That means the distance between them shrinks by exactly 1 every step.

If the gap is 5, it becomes 4, then 3, then 2, then 1, then 0. They meet. The gap cannot stay the same, and it cannot jump over zero to become negative (in the modular sense). It decreases by exactly 1 each time. So they are guaranteed to collide.

This works no matter how large the cycle is, no matter where slow enters it, and no matter what the gap is when both are inside.

The "gap shrinks by 1 each step" argument is the core of Floyd's algorithm. It is worth memorizing. Interviewers love asking why this works, and this one sentence is the complete answer.

The solution

def hasCycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

Five lines of logic. Let's break them down:

Initialize: Both pointers start at the head.
Loop condition: fast and fast.next ensures we do not dereference null. If fast reaches the end, no cycle exists.
Move slow one step forward.
Move fast two steps forward.
Check: If they are at the same node, cycle found.

If the loop exits naturally (fast hit null), return false.

Why check fast.next in the loop condition? Because fast moves two steps. If fast.next is null, then fast.next.next would crash. You always need to check one step ahead when moving two.

Drill this solution with spaced repetition

Complexity analysis

Time: O(n). If there is no cycle, fast reaches the end in n/2 steps. If there is a cycle, once both pointers are in the cycle, they meet within at most one full loop of the cycle. Either way, the total steps are proportional to n.

Space: O(1). Two pointer variables. That is it. No hash set, no extra data structure. This is the whole point of Floyd's algorithm.

Approach	Time	Space
Hash set	O(n)	O(n)
Floyd's tortoise and hare	O(n)	O(1)

Edge cases

Empty list (head is null). The while condition fails immediately. Return false. Correct.
Single node, no cycle. fast.next is null. Loop does not execute. Return false. Correct.
Single node pointing to itself. After one step, slow == fast. Return true. Correct.
Cycle at the very beginning. The tail points back to the head. Works fine, fast catches slow quickly.
Very long tail before the cycle starts. No problem. Fast enters the cycle first and waits (keeps looping) until slow arrives. Then the gap-closing begins.

The Building Blocks

This problem is built from one core building block:

Fast-slow pointer (Floyd's cycle detection). Two pointers moving at different speeds through a linked list. If they meet, there is a cycle. The slow pointer moves one step, the fast pointer moves two. The gap between them closes by exactly one each iteration, guaranteeing they collide if a cycle exists.

This building block shows up in more problems than you might expect:

Linked List Cycle II (LeetCode 142) extends this technique. After detecting the cycle, you need to find the exact node where the cycle begins. The trick: reset one pointer to the head, then move both at speed 1. They meet at the cycle start. Same underlying algorithm, deeper application.
Happy Number (LeetCode 202) is a disguised cycle detection problem. The sequence of digit-squared sums either reaches 1 or loops. You can use Floyd's algorithm on the sequence itself, no linked list needed.
Find the Duplicate Number (LeetCode 287) uses the array values as next-pointers to create an implicit linked list. Detecting the duplicate is exactly cycle detection. This is one of the most elegant applications of Floyd's algorithm.
Middle of the Linked List (LeetCode 876) uses the same two-pointer setup. When fast reaches the end, slow is at the middle. Not cycle detection, but the same core idea of different-speed traversal.
Palindrome Linked List (LeetCode 234) uses fast-slow to find the midpoint, then reverses the second half to compare.

Once you internalize the fast-slow pointer pattern, you start spotting it everywhere. It is not just about cycles. It is about using speed differences to extract structural information from a sequence.

Why you will forget this (and what to do about it)

Floyd's algorithm is one of those solutions that feels obvious once you see it, but is surprisingly hard to reproduce from scratch. The loop condition (fast and fast.next), the pointer initialization, the comparison after moving (not before). Small details, but getting any one of them wrong means a broken solution.

The fix is the same as always: type it from memory, repeatedly, with increasing gaps between sessions. After three or four reps, the pattern locks in and you stop second-guessing the order of operations.

Try CodeBricks free

Reverse Linked List - Another fundamental linked list technique that tests your pointer manipulation skills
Two Pointer Pattern - The general pattern behind fast and slow pointers, applied to arrays