Cycle Detection with Floyd's Algorithm
Detect cycles using the slow-fast pointer approach, find the entry point of the cycle, and prove the algorithm's correctness mathematically.
Cycle Detection with Floyd's Algorithm is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is a Cycle in a Linked List?
A cycle in a linked list occurs when a node's next pointer points back to a previously visited node, creating an infinite loop. Traversing such a list with a while head loop would run forever. Cycle detection is a classic interview problem and the foundation of more advanced pointer algorithms.
The naive approach stores every visited node in a set and checks for membership — O(n) time, O(n) space. Floyd's algorithm solves the same problem in O(n) time and O(1) space, which is what interviewers expect.
Floyd's Slow-Fast Pointer Algorithm
Floyd's cycle detection (the 'tortoise and hare') uses two pointers: slow advances one step at a time, fast advances two steps. If no cycle exists, fast reaches None first. If a cycle exists, fast eventually laps slow inside the cycle and they meet at the same node. The meeting proves a cycle exists.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1] # cycle: -4 -> 2
print(hasCycle(nodes[0])) # TrueWhy Slow and Fast Always Meet
Informally: once both pointers enter the cycle, the distance between them changes by 1 per step (fast gains 2, slow gains 1, so the gap closes by 1 each round). Eventually the gap becomes 0 — they are at the same node. More formally, if the cycle has length C, the maximum gap inside the cycle is C-1, and the gap closes by 1 each step, so they meet within C steps after both enter the cycle.
Total steps before meeting: at most O(n + C) = O(n) since C <= n.
# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
gap = start_gap
steps = 0
while gap != 0:
gap = (gap - 1) % cycle_length
steps += 1
print(f'Start gap {start_gap}: meet after {steps} step(s)')Finding the Cycle Entry Point
After detecting a cycle, Floyd's algorithm can also find the entry node (where the cycle begins). After slow and fast meet inside the cycle, reset one pointer to the head and keep the other at the meeting point. Then advance both by one step at a time. They will meet exactly at the cycle entry node. This works because the distance from head to entry equals the distance from the meeting point to entry (mod cycle length).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
slow = fast = head
# Phase 1: detect meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find entry
pointer = head
while pointer is not slow:
pointer = pointer.next
slow = slow.next
return pointer # cycle entry node
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1] # entry is nodes[1] (val=2)
entry = detectCycle(nodes[0])
print(entry.val) # 2Mathematical Proof of Entry Node
Let F = distance from head to cycle entry, C = cycle length, and a = distance from entry to meeting point inside cycle. When they meet: slow has traveled F + a steps; fast has traveled F + a + n*C steps (n complete loops ahead). Since fast = 2 * slow: 2(F+a) = F+a+nC → F = nC - a. This means distance from head to entry equals distance from meeting point to entry (mod C). Resetting one pointer to head and advancing both by 1 converges them at the entry node.
# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1 # head(3) to entry(2)
C = 3 # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')Cycle Length Measurement
Once you have the meeting point inside the cycle (phase 1 of Floyd's), you can measure the cycle length: keep one pointer stationary and advance the other until they meet again. The number of steps taken equals the cycle length. This is useful for problems that ask for the cycle length explicitly.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def cycle_length(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # found meeting point
length = 1
fast = fast.next
while fast is not slow:
fast = fast.next
length += 1
return length
return 0 # no cycle
nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2] # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0])) # 3Happy Number (Cycle Detection Without a List)
Floyd's algorithm is not limited to linked lists. LeetCode 202 'Happy Number' asks whether repeatedly replacing n with the sum of squares of its digits eventually reaches 1. If it enters a cycle that does not include 1, it will loop forever. You can model this as virtual linked-list traversal where each node's 'next' is the next computed value — then apply Floyd's to detect the cycle.
def isHappy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow, fast = n, next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(isHappy(19)) # True (1->81+1=82->68->100->1)
print(isHappy(2)) # False (enters cycle)Naive Set-Based Detection vs Floyd's
The set-based approach stores each visited node in a set and checks for membership before visiting. It is O(n) time and O(n) space. Floyd's is also O(n) time but only O(1) space — no extra data structure. In memory-constrained environments (embedded systems, operating system kernels) the O(1) space guarantee matters. Interviewers sometimes explicitly ask for O(1) space as a follow-up after you give the set solution.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Naive O(n) space approach
def hasCycle_set(head):
seen = set()
while head:
if id(head) in seen:
return True
seen.add(id(head))
head = head.next
return False
# Floyd's O(1) space approach
def hasCycle_floyd(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
print('Both implementations give the same result')Edge Cases for Cycle Detection
Three edge cases to handle. First, empty list: head is None — Floyd's loop condition fast and fast.next immediately exits, returning False. Second, single node no cycle: fast.next is None, loop exits, returns False. Third, single node with cycle: node's next points to itself — slow and fast both start at head; after one step fast advances to head.next.next = head, but slow is at head.next = head. Then fast == slow on the very first iteration.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# Edge cases
print(hasCycle(None)) # False: empty
node = ListNode(1)
print(hasCycle(node)) # False: single, no cycle
node.next = node
print(hasCycle(node)) # True: single node cycleLinked List Cycle II: LeetCode 142
LeetCode 142 'Linked List Cycle II' asks for the node where the cycle begins (or None if no cycle). This is the direct application of the two-phase Floyd's algorithm. Interviewers ask this as a follow-up to the basic cycle detection. The full solution: phase 1 finds the meeting point inside the cycle; phase 2 resets one pointer to head and walks both forward until they meet — that meeting point is the cycle entry.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
slow = fast = head
# Phase 1
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None
# Phase 2
ptr = head
while ptr is not slow:
ptr = ptr.next
slow = slow.next
return ptr
nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2] # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val) # 3Why Floyd's Beats the Set Approach
While both approaches are O(n) time, the constant factor differs in practice. The set approach must hash each node pointer (compute hash, probe the hash table, store the pointer), whereas Floyd's only performs pointer dereferences — much cheaper per step. More importantly, the O(1) space guarantee means Floyd's can run on arbitrarily long lists without risk of running out of memory.
Mentioning this space advantage proactively in an interview signals deep understanding of algorithmic trade-offs beyond the raw Big-O notation.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Floyd's slow-fast pointer algorithm detects cycles in O(n) time and O(1) space, phase 2 (reset one pointer to head, advance both by 1) finds the exact cycle entry node, and the same technique applies beyond linked lists to any implicit sequence where 'next' is a function. Next up we cover merging sorted lists, splitting lists at midpoints, and finding the nth node from the end.
Frequently asked questions
Is the “Cycle Detection with Floyd's Algorithm” lesson free?
Yes — the full text of “Cycle Detection with Floyd's Algorithm” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Cycle Detection with Floyd's Algorithm”?
Detect cycles using the slow-fast pointer approach, find the entry point of the cycle, and prove the algorithm's correctness mathematically. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Cycle Detection with Floyd's Algorithm” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Node Class and List Construction
- Reversing a Linked List
- Cycle Detection with Floyd's Algorithm
- Merge, Split, and Find Nth from End