Linked list cycle detection (Floyd) Explained: Tracing 1→2→3→4→5→3…
Master Floyd's cycle-finding algorithm with a step-by-step trace of 1→2→3→4→5→3. Build the tortoise-and-hare mental model and handle acyclic edge cases.
By Learnisim AI·Published September 22, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
Why Naive Linked List Traversal Fails on Cyclic Pointers
Phase 1: The Infinite Trap of Linked List Cycles
Imagine you are handed a standard singly linked list representation where the head node points to 1, which points to 2, 3, 4, 5, and then node 5 points backward to node 3. You are given the task of determining whether this structure terminates cleanly or loops forever. If you write a standard linear traversal that checks current = current.next until current == null, your program will run forever, chewing up CPU cycles without ever returning a boolean result.
Without a mechanism to detect a loop, linear data structures that contain circular back-pointers become unnavigable traps. In memory-constrained environments, you cannot simply allocate a growing hash set of visited node references either, because doing so requires O(N) extra space that defeats the pointer-only nature of the list. We need a way to detect whether we are walking in circles without remembering every single step we have taken.
Why Naive Linked List Traversal Fails on Cyclic Pointers diagram
Model
The Tortoise and Hare Model: Pacing Two Pointers
Phase 2: The Two-Pointer Racetrack
Imagine two runners on a circular track. One runner jogs at a normal pace, while the second runner sprints at twice that speed. If the track has a straightaway that ends in a dead end (an acyclic list like 1→2→3→null), the sprinter will reach the end of the road and stop. But if the track loops back on itself, the sprinter will eventually lap the jogger from behind.
In our locked working example, the list has a cycle: 1→2→3→4→5→3… where node 5 points back to node 3. Let us set a slow pointer to move forward by 1 step (.next) at a time, and a fast pointer to move forward by 2 steps (.next.next) at a time. Both pointers start together at node 1.
As time ticks forward, the distance between the fast pointer and the slow pointer changes deterministically. If there is no cycle, the fast pointer hits a null pointer and the game ends safely. If there is a cycle, the fast pointer wraps around the loop and closes the gap on the slow pointer until both land on the exact same memory address.
The Tortoise and Hare Model: Pacing Two Pointers diagram
Syntax
Syntax and Implementation of Floyd's Cycle-Finding Algorithm
Phase 3: Syntax & APIs
Now that you understand how pacing works conceptually, we need to translate those two independent speeds into precise code syntax. For our locked working example, we inspect a node structure where each element has a value and a next reference.
To implement Floyd's algorithm, we declare two pointers, slow and fast, both starting at the list's head (1). Inside a while loop, we advance slow by a single step using slow = slow.next and fast by two steps using fast = fast.next.next. We must guard against null references so we do not attempt to read next on a null tail (which occurs in our acyclic baseline 1→2→3→null).
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head: ListNode) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
A common syntax mistake is checking while fast.next and fast instead of while fast and fast.next. Because Python uses short-circuit evaluation, checking fast.next first when fast is null will instantly raise an AttributeError. Another frequent trap is forgetting to advance both pointers inside the loop, leading to an accidental infinite loop in your traversal logic.
python
def hasCycle(head: ListNode) -> bool:
# Complete the tortoise and hare traversal syntax here
pass
Worked example
Tracing Floyd's Algorithm Step by Step on 1→2→3→4→5→3…
Phase 4: Worked Example
To see Floyd's Cycle-Finding Algorithm in action, let us trace our locked example: a linked list with nodes 1 → 2 → 3 → 4 → 5, where node 5.next points back to node 3. We will also contrast this with an acyclic list 1 → 2 → 3 → null to observe how the fast pointer safely exits without crashing.
Given
- Cyclic Input: head points to node 1. The sequence flows 1 → 2 → 3 → 4 → 5, and 5.next = 3 (creating a cycle of length 3: nodes 3, 4, 5). - Acyclic Input: head points to node 1. The sequence flows 1 → 2 → 3 → null. - Pointers: slow and fast both start at head (1).
1. Initialization: slow = 1, fast = 1. 2. Iteration 1: slow=2, fast=3. 3. Iteration 2: slow=3, fast=null. Loop terminates because fast is null.
Result
- For the cyclic list, slow and fast meet at node 4, returning true. - For the acyclic list, fast hits null, returning false without entering an infinite loop.
python
def has_cycle(head):
# Trace the algorithm for: 1 -> 2 -> 3 -> 4 -> 5 -> 3...
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Tracing Floyd's Algorithm Step by Step on 1→2→3→4→5→3… diagram
Practice
Practice Writing and Tracing Floyd's Cycle Detection Loop
Now that you have traced how the slow and fast pointers converge inside the cyclic list 1→2→3→4→5→3… and safely hit null on an acyclic list, it is time to write the logic yourself. Apply the pointer-advancement rules you learned in the syntax and worked phases to solve a short code completion task. Remember to protect against null pointer exceptions when advancing your fast pointer twice.
javascript
function hasCycle(head) {
if (!head || !head.next) return false;
let slow = head;
let fast = head;
// Complete the while loop and pointer movements
while (/* condition */) {
// Advance slow by 1 and fast by 2
}
return false;
}
Now that you have mastered detecting whether a cycle exists in our working example 1->2->3->4->5->3..., let's tackle a classic follow-up problem that demands a deeper transfer of the tortoise and hare pattern: finding the exact starting node of the cycle.
In our cyclic list 1->2->3->4->5->3..., the cycle begins at node 3. If your interviewer or application requires you to return the node 3 instead of just a boolean true, how do you adapt Floyd's algorithm? The naive approach uses a hash set to store visited addresses, but that violates our O(1) space complexity constraint.
Instead, we leverage a geometric property of meeting points. When the slow pointer (traveling 1 step at a time) and the fast pointer (traveling 2 steps at a time) finally meet at node 4 inside the loop, the distance from the head of the list to the cycle start (1 to 3) is mathematically guaranteed to equal the distance from the meeting point (4) around the loop back to the cycle start (3).
To apply this transfer, write a function that takes the head of a cyclic linked list, runs standard Floyd's detection until slow === fast, and then resets one pointer back to head. Advancing both pointers synchronously by 1 step per iteration will cause them to collide precisely at the cycle start node.
Given the linked list 1->2->3->4->5->3..., trace how resetting one pointer to head while keeping the other at the meeting node (4) resolves the cycle start to node 3 in exactly two steps.
javascript
function detectCycleStart(head) {
let slow = head;
let fast = head;
// Phase 1: Detect intersection
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
// Phase 2: Find cycle start
let pointer = head;
while (pointer !== slow) {
pointer = pointer.next;
slow = slow.next;
}
return pointer;
}
}
return null; // Acyclic
}
FAQ
What happens when Floyd's algorithm runs on the acyclic list 1→2→3→null?
The fast pointer (hare) will reach the null tail and terminate the loop safely, returning false to indicate no cycle exists.
Why do the slow and fast pointers always meet inside a cycle?
The fast pointer moves two steps while the slow pointer moves one, closing the gap by one node per step within the circular path.
What is the time and space complexity of Floyd's cycle detection algorithm?
It runs in O(N) time complexity for both cyclic and acyclic lists, and O(1) constant space complexity because it only uses two pointer variables.
![Prereqs [[1,0],[2,0],[3,1],[3,2]] vs a 2-cycle [[1,0],[0,1]] overview diagram](/blogs/topological-sort-explained-valid-vs-cyclic-course-schedules/diagrams/hero.svg)
