Introduction

Cycle detection in a linked list determines whether a sequence of nodes eventually loops back to a previously visited node. The two primary algorithms are the hash set approach (O(n) time, O(n) space) and Floyd's tortoise and hare algorithm (O(n) time, O(1) space). Floyd's algorithm is the standard interview solution because it uses constant space. Beyond detection, these algorithms can find the cycle start node and compute the cycle length.

What Is a Cycle?

A cycle exists when a node's next pointer points back to a previous node, creating an infinite loop:

1Normal list:    1 → 2 → 3 → 4 → null
2
3Cycle present:  1 → 2 → 3 → 4
4                     ↑         |
5                     └─────────┘

Node 4's next points to node 2, so traversing from node 2 onward loops forever (2 → 3 → 4 → 2 → ...).

Algorithm 1: Hash Set

Store visited nodes in a set. If you encounter a node already in the set, a cycle exists:

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def has_cycle_hashset(head):
7    visited = set()
8    current = head
9
10    while current:
11        if id(current) in visited:
12            return True  # Cycle detected
13        visited.add(id(current))
14        current = current.next
15
16    return False  # Reached null — no cycle

• Time complexity: O(n) — visit each node at most once
• Space complexity: O(n) — store up to n node references

Algorithm 2: Floyd's Tortoise and Hare (Optimal)

Use two pointers: slow (moves 1 step) and fast (moves 2 steps). If a cycle exists, fast catches slow inside the cycle:

1def has_cycle(head):
2    slow = head
3    fast = head
4
5    while fast and fast.next:
6        slow = slow.next        # Move 1 step
7        fast = fast.next.next   # Move 2 steps
8
9        if slow == fast:
10            return True  # Pointers met — cycle exists
11
12    return False  # Fast reached null — no cycle

• Time complexity: O(n) — fast enters cycle, gap closes by 1 each step
• Space complexity: O(1) — only two pointers

Why It Works

When both pointers are inside a cycle of length C:

• Each step, fast gains 1 node on slow (fast moves 2, slow moves 1)
• The gap between them decreases by 1 per step
• After at most C steps, fast catches slow (gap becomes 0)

Finding the Cycle Start Node

After detection, find where the cycle begins:

1def find_cycle_start(head):
2    slow = head
3    fast = head
4
5    # Phase 1: Detect cycle
6    while fast and fast.next:
7        slow = slow.next
8        fast = fast.next.next
9        if slow == fast:
10            break
11    else:
12        return None  # No cycle
13
14    # Phase 2: Find start
15    # Move one pointer to head, keep the other at meeting point
16    # Both move 1 step — they meet at cycle start
17    slow = head
18    while slow != fast:
19        slow = slow.next
20        fast = fast.next
21
22    return slow  # Cycle start node

Mathematical Proof

Let:

• L = distance from head to cycle start
• C = cycle length
• K = distance from cycle start to meeting point

When they meet: slow traveled L + K steps, fast traveled 2(L + K) steps. Fast also made extra laps: 2(L + K) - (L + K) = L + K extra nodes = multiple of C. So L + K = nC for some integer n, meaning L = nC - K. Moving L steps from the meeting point lands at the cycle start.

Finding the Cycle Length

After detecting the meeting point, count the cycle length:

1def cycle_length(head):
2    slow = head
3    fast = head
4
5    while fast and fast.next:
6        slow = slow.next
7        fast = fast.next.next
8        if slow == fast:
9            # Count cycle length
10            length = 1
11            current = slow.next
12            while current != slow:
13                length += 1
14                current = current.next
15            return length
16
17    return 0  # No cycle

Java Implementation

1public class Solution {
2    public boolean hasCycle(ListNode head) {
3        ListNode slow = head, fast = head;
4
5        while (fast != null && fast.next != null) {
6            slow = slow.next;
7            fast = fast.next.next;
8            if (slow == fast) return true;
9        }
10
11        return false;
12    }
13
14    public ListNode detectCycle(ListNode head) {
15        ListNode slow = head, fast = head;
16
17        while (fast != null && fast.next != null) {
18            slow = slow.next;
19            fast = fast.next.next;
20            if (slow == fast) {
21                slow = head;
22                while (slow != fast) {
23                    slow = slow.next;
24                    fast = fast.next;
25                }
26                return slow;
27            }
28        }
29
30        return null;
31    }
32}

C++ Implementation

1struct ListNode {
2    int val;
3    ListNode* next;
4    ListNode(int x) : val(x), next(nullptr) {}
5};
6
7bool hasCycle(ListNode* head) {
8    ListNode* slow = head;
9    ListNode* fast = head;
10
11    while (fast && fast->next) {
12        slow = slow->next;
13        fast = fast->next->next;
14        if (slow == fast) return true;
15    }
16
17    return false;
18}

Algorithm Comparison

Common Pitfalls

• Not checking fast.next before advancing fast by 2: If fast is on the last node, fast.next.next dereferences null. Always check both fast != null and fast.next != null in the while condition.
• Comparing node values instead of node references: Cycle detection requires checking if two pointers reference the same node object (slow == fast), not if they have the same value (slow.val == fast.val). Different nodes can have identical values.
• Assuming a cycle always starts at the head: The cycle start can be any node in the list. The tail node's next may point to the head, the middle, or even itself. Floyd's phase 2 handles all cases.
• Modifying the list during detection: Some approaches mark visited nodes by changing their values or pointers. This is destructive and makes the list unusable afterward. Floyd's algorithm is non-destructive.
• Forgetting the else clause on the while loop for phase 2: In Python, if the while loop completes without breaking (no cycle), you must return None before executing phase 2. Without this check, phase 2 runs on a non-cyclic list and produces incorrect results.

Summary

• Floyd's tortoise and hare algorithm detects cycles in O(n) time and O(1) space
• Slow pointer moves 1 step, fast pointer moves 2 steps — they meet inside the cycle if one exists
• To find the cycle start: reset one pointer to head, advance both by 1 step until they meet
• Cycle length: after detection, count steps until you return to the meeting point
• Always check fast != null && fast.next != null to prevent null pointer errors