How to Solve: Linked List Cycle Detection (Floyd’s Tortoise and Hare) – Complete Guide

How to Solve: Linked List Cycle Detection (Floyd’s Tortoise and Hare) – Complete Guide

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—nail it and you show clear problem-solving maturity, not just brute-force thinking."

? WHAT YOU NEED TO KNOW FIRST

Before tackling cycle detection, ensure you understand: 1. Linked List Basics – Node structure, traversal, and pointer manipulation. 2. Two-Pointer Techniques – Slow/fast pointers for linear time solutions. 3. Cycle Detection Intuition – Why a cycle means a pointer revisits a node.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this every time you see a cycle detection problem:

1. Clarify Input/Output
2. Confirm the list is singly linked (no backward pointers).

3. Ask: "Is an empty list or single-node list considered a cycle?" (Usually no.)

4. Choose the Right Technique

5. Floyd’s Algorithm → O(1) space, O(n) time (preferred).

6. Hash Set → O(n) space, O(n) time (fallback if Floyd’s is unclear).

7. Initialize Two Pointers

8. slow = head, fast = head.

9. Edge case: If head is null, return false.

10. Traverse the List

11. Move slow by 1 step, fast by 2 steps.
12. If fast reaches null → no cycle.

13. If slow == fast → cycle exists.

14. Handle Follow-Ups (If Asked)

15. Cycle Length: After meeting, keep one pointer fixed, move the other until they meet again. Count steps.

16. Cycle Start: After meeting, reset one pointer to head, move both at 1 step until they meet.

17. Test Edge Cases

18. Empty list.
19. Single-node list (no cycle).
20. Single-node list with cycle (points to itself).

21. Large list with cycle at the end.

22. Code & Optimize

23. Write clean, modular code.
24. Avoid infinite loops (ensure fast.next exists before moving).

? WORKED EXAMPLES

Example 1 – Basic: Detect Cycle (LeetCode 141)

Problem: Given head of a linked list, return true if there’s a cycle.

Thought Process

1. Clarify: No backward pointers, cycle means a node is revisited.
2. Technique: Floyd’s Tortoise and Hare (O(1) space).
3. Initialize: slow = head, fast = head.
4. Traverse:
5. Move slow by 1, fast by 2.
6. If fast reaches null → no cycle.
7. If slow == fast → cycle exists.

Python Code

def hasCycle(head):

    if not head:

        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

Complexity

• Time: O(n) – Fast pointer traverses at most 2n steps.
• Space: O(1) – Only two pointers used.

Why This Works

• If no cycle, fast reaches null first.
• If cycle exists, fast laps slow and they meet.

Example 2 – Medium: Find Cycle Start (LeetCode 142)

Problem: Return the node where the cycle begins.

Thought Process

1. Detect Cycle: Use Floyd’s algorithm to find a meeting point.
2. Find Start:
3. Reset slow to head.
4. Move slow and fast at 1 step each until they meet.
5. The meeting point is the cycle start.

Python Code

def detectCycle(head):

    if not head:

        return None


    slow = head

    fast = head


    # Find meeting point

    while fast and fast.next:

        slow = slow.next

        fast = fast.next.next

        if slow == fast:

            break


    # No cycle

    if not fast or not fast.next:

        return None


    # Find cycle start

    slow = head

    while slow != fast:

        slow = slow.next

        fast = fast.next


    return slow

Complexity

• Time: O(n) – Two passes (one to detect cycle, one to find start).
• Space: O(1) – Only two pointers.

Why This Works

• After meeting, the distance from head to cycle start = distance from meeting point to cycle start.

Example 3 – Hard/Follow-Up: Find Cycle Length

Problem: Return the length of the cycle.

Thought Process

1. Detect Cycle: Use Floyd’s to find a meeting point.
2. Calculate Length:
3. Keep one pointer fixed.
4. Move the other until they meet again, counting steps.

Python Code

def cycleLength(head):

    if not head:

        return 0


    slow = head

    fast = head


    # Find meeting point

    while fast and fast.next:

        slow = slow.next

        fast = fast.next.next

        if slow == fast:

            break


    if not fast or not fast.next:

        return 0


    # Calculate cycle length

    length = 1

    fast = fast.next

    while slow != fast:

        fast = fast.next

        length += 1


    return length

Complexity

• Time: O(n) – One pass to detect cycle, one pass to count length.
• Space: O(1) – Only two pointers.

Why This Works

• After meeting, the cycle length is the number of steps to meet again.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Cycle detection in linked lists? You’ve got two options: Floyd’s Tortoise and Hare or a hash set. Floyd’s is the gold standard—O(1) space, O(n) time. Here’s the playbook:

1. Initialize two pointers: slow and fast, both at head.
2. Traverse: slow moves 1 step, fast moves 2 steps. If fast hits null, no cycle.
3. If they meet: Cycle exists. For follow-ups:
4. Cycle start: Reset slow to head, move both at 1 step until they meet.
5. Cycle length: Keep one fixed, move the other until they meet again, counting steps.
6. Edge cases: Empty list, single node, cycle at the end—test them all.

This isn’t just about memorizing code. It’s about proving you can derive the solution under pressure. Walk in, write clean code, and explain the math. You’ve got this."

? Final Notes

• Practice: Implement Floyd’s algorithm 3 times without looking.
• Whiteboard: Draw the list and pointers to visualize the meeting point.
• Follow-Ups: Be ready for cycle start, length, or even reversing the cycle.

Now go crush that interview. ?