# How to Detect a Cycle in a Linked List Using Floyd’s Tortoise and Hare Algorithm > Detect a cycle in a linked list efficiently with Floyd's Tortoise and Hare algorithm. Learn how two pointers moving at different speeds reveal loops. - Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews) - Tags: how-to-guide - Published: 2026-03-04 --- **Floyd’s Tortoise and Hare algorithm detects a cycle in a linked list by moving two pointers at different speeds—one step at a time for the slow pointer and two steps for the fast pointer—returning true if they meet inside a loop or false if the fast pointer reaches the end.** Detecting a cycle in a linked list is a fundamental interview problem solved optimally with constant space using the two-pointer technique known as Floyd’s cycle detection. The **kdn251/interviews** repository provides battle-tested Java implementations of this algorithm across LeetCode and company-specific modules. This guide walks through the exact implementation found in [`leetcode/two-pointers/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/leetcode/two-pointers/LinkedListCycle.java) and explains why this approach guarantees **O(n)** time complexity with **O(1)** auxiliary space. ## Algorithm Overview The **Tortoise and Hare** strategy relies on two pointers traversing the list at different velocities: - **Slow pointer (Tortoise)**: Advances one node per iteration (`slow = slow.next`) - **Fast pointer (Hare)**: Advances two nodes per iteration (`fast = fast.next.next`) If the list is **acyclic**, the fast pointer reaches the end (`null`) first, terminating the search. If the list contains a **cycle**, the fast pointer eventually laps the slow pointer from behind, causing them to reference the same node. This meeting point proves the existence of a loop. ## Implementation Details The repository implements this logic in the `hasCycle(ListNode head)` method. You can find identical implementations across multiple interview preparation tracks, including: - [`leetcode/two-pointers/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/leetcode/two-pointers/LinkedListCycle.java) - [`company/microsoft/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/company/microsoft/LinkedListCycle.java) - [`company/amazon/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/company/amazon/LinkedListCycle.java) - [`company/bloomberg/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/company/bloomberg/LinkedListCycle.java) ### The Core Method According to the source code in [`leetcode/two-pointers/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/leetcode/two-pointers/LinkedListCycle.java), the implementation handles edge cases first, then enters a traversal loop: ```java public boolean hasCycle(ListNode head) { // Edge case: empty list or single node without a next pointer → no cycle if (head == null || head.next == null) { return false; } // Initialize pointers ListNode slow = head; // moves 1 step ListNode fast = head.next; // moves 2 steps (starts one step ahead) // Traverse until fast reaches the end or meets slow while (fast != null && fast.next != null && fast != slow) { slow = slow.next; // one step fast = fast.next.next; // two steps } // If fast and slow met, a cycle exists return fast == slow; } ``` **Key implementation details:** 1. **Initialization**: The fast pointer starts at `head.next` rather than `head` to ensure the while-loop condition `fast != slow` works correctly from the first iteration. 2. **Null checks**: The loop condition verifies both `fast != null` and `fast.next != null` to prevent `NullPointerException` when advancing the fast pointer. 3. **Termination**: The method returns `true` only when `fast == slow`, confirming the pointers converged inside a cycle. ## Practical Code Examples ### Example 1: Handcrafted Cycle Detection ```java // Build nodes ListNode a = new ListNode(1); ListNode b = new ListNode(2); ListNode c = new ListNode(3); a.next = b; b.next = c; c.next = a; // creates a cycle (c → a) // Detect cycle Solution sol = new Solution(); System.out.println(sol.hasCycle(a)); // prints: true ``` ### Example 2: Dynamic List with Injected Cycle ```java // Assume we have a utility that builds a linked list from an array int[] values = {4, 5, 6, 7}; ListNode head = ListBuilder.fromArray(values); // no cycle initially Solution sol = new Solution(); System.out.println(sol.hasCycle(head)); // prints: false // Introduce a cycle for testing head.next.next.next.next = head.next; // tail points to second node System.out.println(sol.hasCycle(head)); // prints: true ``` ### Example 3: LeetCode-Style Runner ```java public class Main { public static void main(String[] args) { // Example list: 1 → 2 → 3 → 4 → 2 (cycle starts at node with value 2) ListNode n1 = new ListNode(1); ListNode n2 = new ListNode(2); ListNode n3 = new ListNode(3); ListNode n4 = new ListNode(4); n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2; // creates cycle Solution solution = new Solution(); System.out.println(solution.hasCycle(n1)); // true } } ``` ## Why This Algorithm Works In an acyclic list, the fast pointer moves twice as fast toward the null terminator. Since it starts ahead and moves two steps per iteration, it will always reach `null` before or at the same time the slow pointer reaches the final node. In a cyclic list, once both pointers enter the loop, the distance between them changes by exactly one node per iteration (the fast pointer gains one node on the slow pointer each step). Because the loop length is finite, the fast pointer will eventually close the gap and occupy the same node as the slow pointer, confirming the cycle. This convergence is mathematically guaranteed regardless of the cycle's length or entry point. ## Complexity Analysis - **Time Complexity**: **O(n)** where n is the number of nodes. In the worst case, the algorithm traverses the list once before finding the cycle or reaching the end. - **Space Complexity**: **O(1)** auxiliary space. The solution uses only two pointer variables (`slow` and `fast`) regardless of input size, unlike hash-based approaches that require **O(n)** space to store visited nodes. ## Summary - Floyd’s Tortoise and Hare algorithm uses two pointers moving at 1x and 2x speeds to detect cycles without extra data structures. - The `hasCycle()` method in [`leetcode/two-pointers/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/leetcode/two-pointers/LinkedListCycle.java) initializes `fast` at `head.next` and iterates until pointers meet or `fast` reaches null. - This approach guarantees linear time complexity while maintaining constant space overhead, making it optimal for embedded or memory-constrained environments. - The kdn251/interviews repository duplicates this implementation across company-specific directories (Microsoft, Amazon, Bloomberg), demonstrating its universal applicability in technical interviews. ## Frequently Asked Questions ### Why does Floyd’s algorithm use two pointers moving at different speeds? The different speeds ensure that if a cycle exists, the fast pointer will eventually lap the slow pointer from behind. If both pointers moved at the same speed, they would maintain a constant distance inside a cycle and never meet unless they started at the exact same node. The 2:1 speed differential guarantees the distance between them decreases by one node per iteration inside the loop, forcing convergence. ### Can I use a HashSet to detect a cycle instead of Floyd’s algorithm? Yes, but it requires **O(n)** space complexity. You would traverse the list while storing node references in a `HashSet`, returning `true` if `set.add(node)` returns false (indicating the node was visited before). While simpler to implement, this approach consumes memory proportional to the list length, whereas Floyd’s algorithm detects a cycle in a linked list using only two pointers with **O(1)** space. ### What happens if both pointers start at the head instead of offsetting the fast pointer? If both `slow` and `fast` start at `head` and you check for equality after moving both pointers, the loop condition must be structured carefully to avoid immediate false positives (they start equal). The implementation in [`leetcode/two-pointers/LinkedListCycle.java`](https://github.com/kdn251/interviews/blob/main/leetcode/two-pointers/LinkedListCycle.java) avoids this by initializing `fast = head.next`, ensuring the first comparison happens after at least one movement. Both initialization patterns work if the loop logic is adjusted accordingly. ### How do I find the start of the cycle once detected? Once the tortoise and hare meet, reset one pointer to the head while keeping the other at the meeting point. Then advance both pointers one step at a time. The node where they meet again is the start of the cycle. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start when measured along the loop.