Introduction

Cycle detection in linked lists can be done in linear time while using only two pointer variables. The standard solution is Floyd’s tortoise-and-hare algorithm, where one pointer moves one step and the other moves two steps. If a cycle exists, they eventually meet; if not, the fast pointer reaches null.

Core Sections

Why Two Pointers Are Enough

A linked list with no cycle has a natural end. A fast pointer moving twice as quickly will always hit that end first. In a cyclic list, the fast pointer repeatedly laps the slow pointer inside the cycle, so the distance between them eventually becomes zero.

This gives:

• time complexity linear in node count
• constant additional memory
• no need for hash sets or node marking

The algorithm is both memory-efficient and robust.

Baseline Implementation in Python

1class Node:
2    def __init__(self, value):
3        self.value = value
4        self.next = None
5
6
7def has_cycle(head: Node | None) -> bool:
8    slow = head
9    fast = head
10
11    while fast is not None and fast.next is not None:
12        slow = slow.next
13        fast = fast.next.next
14
15        if slow is fast:
16            return True
17
18    return False

This function only stores slow and fast pointers plus loop-local state.

Building Test Cases

Create both acyclic and cyclic lists to verify behavior.

1# acyclic list
2n1 = Node(1)
3n2 = Node(2)
4n3 = Node(3)
5n1.next = n2
6n2.next = n3
7print(has_cycle(n1))  # False
8
9# cyclic list
10c1 = Node("a")
11c2 = Node("b")
12c3 = Node("c")
13c1.next = c2
14c2.next = c3
15c3.next = c2  # cycle back
16print(has_cycle(c1))  # True

Testing both shapes prevents false confidence from single-case validation.

Finding the Cycle Entry Point

After detection, you can locate the exact node where cycle begins without extra memory. Reset one pointer to head, keep the other at meeting point, then move both one step at a time.

1def cycle_entry(head: Node | None) -> Node | None:
2    slow = head
3    fast = head
4
5    while fast is not None and fast.next is not None:
6        slow = slow.next
7        fast = fast.next.next
8        if slow is fast:
9            break
10    else:
11        return None
12
13    seeker = head
14    while seeker is not slow:
15        seeker = seeker.next
16        slow = slow.next
17
18    return seeker

This extension is useful in debugging corrupted pointer structures.

Why the Meeting Proof Works

Inside the cycle, suppose cycle length is k. Each loop iteration increases fast-minus-slow progress by one node modulo k, because fast takes two steps and slow takes one. Modular arithmetic guarantees eventual equality modulo k, so they meet.

This proof explains why algorithm does not miss cycles regardless of where cycle starts.

Edge Cases to Handle

Critical edge conditions:

• empty list
• single node with no cycle
• single node pointing to itself
• long acyclic prefix before cycle

The loop condition fast and fast.next handles most of these safely.

Alternative Method and Tradeoff

Using a set of visited nodes is simpler to reason about but uses linear extra memory.

1def has_cycle_set(head):
2    seen = set()
3    curr = head
4    while curr:
5        if id(curr) in seen:
6            return True
7        seen.add(id(curr))
8        curr = curr.next
9    return False

Choose this when readability matters more than memory constraints.

Common Pitfalls

• Advancing fast pointer incorrectly and causing attribute errors on null nodes.
• Comparing node values instead of node identity.
• Forgetting to test self-loop single-node lists.
• Assuming detection function also returns entry node automatically.
• Accidentally mutating list while traversing and invalidating logic.

Summary

• Floyd’s two-pointer method detects cycles using constant extra memory.
• Fast pointer reaching null means list is acyclic.
• Pointer meeting means cycle exists.
• A second phase can locate cycle entry node without extra memory.
• Edge-case tests are essential for robust linked-list implementations.