Coding interview problems › Linked Lists

🔗 Linked Lists Easy

Linked List Cycle (Floyd's Algorithm)

Detect a cycle in a linked list with Floyd's tortoise and hare: a slow and a fast pointer meet only inside a loop, O(1) space. Tested Python and a live visual.

Also searched as: Floyd's cycle detection · tortoise and hare algorithm · detect loop in linked list

🔗

Try it live Free

Linked Lists: Reverse & Floyd's Cycle

Switch on a cycle in the linked list lab and watch Floyd's tortoise and hare race until they meet inside the loop.

Open the playground →

The problem

Given the head of a singly linked list, return True if following next pointers ever brings you back to a node you have already visited (the list has a cycle), and False if the list ends at None. Try to use O(1) extra memory.

Input3 -> 2 -> 0 -> 4, and 4 points back to 2
OutputTrue
Input1 -> 2 -> None
OutputFalse

The key insight

Send two runners down the list: the tortoise moves one step at a time, the hare two. If the list ends, the hare reaches None first. If there is a loop, both get trapped in it, and the hare gains one step on the tortoise every move, so it must eventually land on the same node.

Brute force first: Storing every visited node in a set and checking for repeats is O(n) time but also O(n) extra memory.

Step-by-step approach

  1. Start slow and fast at head.
  2. While fast and fast.next are not None, move slow one step and fast two steps.
  3. If slow is fast after a move, there is a cycle: return True.
  4. If the loop exits, the hare fell off the end: return False.

Python solution

PYTHON 3tested
class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next


def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # tortoise: 1 step
        fast = fast.next.next       # hare: 2 steps
        if slow is fast:
            return True
    return False

Complexity

TimeO(n)
SpaceO(1)

Without a cycle the hare reaches the end in n/2 moves. With a cycle, once both are inside it the gap closes by one node per move, so they meet within one lap. Only two pointers are stored.

Common mistakes

Frequently asked questions

What is the time and space complexity of Floyd's cycle detection?

O(n) time and O(1) extra space, since only two pointers move along the list.

Why must the fast pointer meet the slow one?

Once both are in the cycle, the distance from the hare to the tortoise shrinks by exactly one each move, so it reaches zero rather than skipping over. They meet within one trip around the loop.

How do I find where the cycle starts?

After they meet, move one pointer back to the head and advance both one step at a time; they meet again at the first node of the cycle. That is Linked List Cycle II.

Is the hash set approach acceptable?

It is correct and easy to explain, and fine as a first answer. Interviewers usually follow up by asking for O(1) space, which is where Floyd's algorithm comes in.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Linked Lists Linked Lists: Reverse & Floyd's Cycle lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.