Why is the relative speed difference of 1 step between slow and fast pointers crucial?

When both pointers are inside the loop, the distance between them reduces by exactly 1 step on every iteration. Since the gap decrements by 1 every tick, it is mathematically guaranteed to reach 0 without the fast pointer ever skipping or leapfrogging over the slow pointer.

Could we solve this with a Hash Table instead?

Yes, you could store visited node memory addresses in a hash table or set. However, that consumes O(n) auxiliary heap memory. Floyd's algorithm solves the problem in O(1) auxiliary space.

EasyLinked ListTwo PointersPattern: Fast and Slow PointersPattern: Floyd's Tortoise and Hare

Linked List Cycle

Determine if a linked list contains a cycle using Floyd's Tortoise and Hare algorithm. The foundational problem for understanding two-speed pointer convergence in finite loops.

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Examples & Constraints

Example 1

Input: head = [3, 2, 0, -4], pos = 1

Output: true

Explanation: There is a cycle in the linked list, where the tail links back to the 1st node (index 1, val 2).

Example 2

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle in the linked list.

Constraints

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Floyd's Tortoise and Hare (Fast & Slow Pointers)

Optimal Approach

Time:O(n)

Space:O(1)

Advance a slow pointer by 1 step and a fast pointer by 2 steps. If a loop exists, the fast runner is guaranteed to lap and intersect the slow runner.

Time ComplexityO(n)

If there is no cycle, fast reaches the end in N/2 iterations. If there is a cycle, slow enters the cycle after K steps and fast catches up in at most C steps. Total steps <= N.

Space ComplexityO(1)

Only two pointer references (slow and fast) are maintained throughout execution.

Underlying algorithmic logic

The Mathematical Intuition: Closing the Gap

Imagine two runners on a circular running track. If Runner A runs at 1 meter/second and Runner B runs at 2 meters/second, the distance between them increases by 1 meter every second.

Because the relative speed difference is exactly 1 step per tick:

When both pointers enter a cycle of length C, the distance between them decreases by 1 step each iteration (gap = (gap - 1) % C).
The fast pointer cannot "jump over" or skip past the slow pointer without landing on the exact same node!
Therefore, if a cycle exists, slow and fast must collide within at most C iterations.
If no cycle exists, fast or fast.next will inevitably hit null, signaling the linear end of the list.

Why Floyd's Algorithm Beats Hash Set

Using a Hash Set to store visited node references requires O(n) heap memory and can be restricted in systems with strict memory allocation limits. Floyd's cycle detection operates strictly with two pointer variables in O(1) auxiliary space without mutating node structures.

Step-by-step execution walkthrough

Initial State

slow and fast both start at head (node 3). List: 3 -> 2 -> 0 -> -4 (links back to 2).

slow = 3, fast = 3

Iteration 1

slow moves 1 step to 2. fast moves 2 steps to 0.

slow = 2, fast = 0

Iteration 2

slow moves 1 step to 0. fast moves 2 steps: -4 then wraps back to 2.

slow = 0, fast = 2

Iteration 3 (Collision)

slow moves 1 step to -4. fast moves 2 steps: 0 then -4. slow == fast!

Collision at node -4 -> return true

Advantages

•Optimal O(1) auxiliary space
•Requires zero node modifications or extra hash tables

Trade-offs

•Does not identify the exact entry point index of the cycle (solved in Linked List Cycle II)

Code Implementations

Ready-to-use

Copy & paste production-ready solutions for Floyd's Tortoise and Hare (Fast & Slow Pointers) in your language of choice

File: solution.py

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def has_cycle(head: ListNode | None) -> bool:
    if not head or not head.next:
        return False
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
if __name__ == "__main__":
    # Create cycle: 3 -> 2 -> 0 -> -4 -> (points back to 2)
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # cycle back to node2
    print("Has cycle:", has_cycle(node1))

Interactive visualizer available

Understand Circular Linked List Visually

Understand node loops where the tail pointer links back to the head node to form a closed circle. Test live edge cases and watch memory state transitions step-by-step.

Launch Circular Linked List Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems

EasyLinked List

Visualizer

Reverse Linked List

Reverse the directional arrows of a singly linked list in-place. The classic test of reference manipulation and memory pointer management.

Merge Two Sorted Lists

Splice together nodes of two sorted linked lists into a single sorted list. The canonical problem for learning pointer reassignment and the dummy head technique.

Valid Palindrome

Determine if a string is a palindrome considering only alphanumeric characters and ignoring case. The canonical problem for learning the two-pointer inward convergence technique.

1 approach(O(n))

Learn logic