Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

A singly linked list may eventually point back to an earlier node instead of ending at None. The task is to return the exact node where that cycle begins, or None if the list has no cycle. The list must not be modified.

Remember that the cycle’s entry is defined by node identity, not by a node’s value. Several nodes may store the same value, so comparing values cannot identify either a cycle or its starting point.

A hash set can record every node already visited and return the first repeated one. That is simple and correct, but it uses O(n) extra space. Floyd’s tortoise-and-hare algorithm reaches the same answer with two pointers and O(1) auxiliary space.

Deriving Floyd’s two-phase solution

The first phase answers whether a cycle exists. Start a slow pointer and a fast pointer at the head. Move the slow pointer one edge per step and the fast pointer two edges per step. If the fast pointer reaches None, the list ends and therefore has no cycle. If there is a cycle, the fast pointer gains one position on the slow pointer during every step around that finite loop, so the two pointers must eventually meet.

That meeting node is not necessarily the cycle’s entry. A second phase locates the entry: leave one pointer at the meeting node, place another at the head, and move both one edge at a time. The node where they meet is the cycle’s first node.

The surprising second phase follows from a short distance argument. Let:

  • a be the number of edges from the head to the cycle entry;
  • b be the number of edges from the entry to the phase-one meeting node, following the cycle; and
  • L be the cycle length.

At the phase-one meeting, the fast pointer has traveled twice as far as the slow pointer. Their distance difference is therefore exactly the slow pointer’s distance, and that difference must be a whole number of laps around the cycle. Consequently, a + b is divisible by L, which means a is congruent to L - b modulo L.

From the meeting node, L - b edges reach the cycle entry. So after the head pointer walks its a edges to the entry, the pointer at the meeting node also lands at the entry, possibly after making additional complete laps. Moving them at equal speed makes that their first shared node in phase two.

Why the algorithm is optimal

If the list is acyclic, the fast pointer reaches its end after examining only a linear number of links. If the list has a cycle, phase one enters that cycle and meets within at most one additional lap; phase two then walks to the entry. The total time is O(n).

Only a fixed number of node references are stored, so auxiliary space is O(1). The list is not changed. A worst-case algorithm cannot do better than O(n) time because the only evidence of a late cycle may be a link near the end of a long list.

Python solution

from __future__ import annotations


# LeetCode provides this class:
# class ListNode:
#     def __init__(self, value: int = 0, next_node: ListNode | None = None):
#         self.val = value
#         self.next = next_node


class CycleEntryFinder:
    """Find a linked-list cycle entry without modifying the list."""

    @classmethod
    def find_entry(cls, head: ListNode | None) -> ListNode | None:
        """Return the cycle's first node, or None when no cycle exists."""
        meeting_node = cls._find_meeting_node(head)
        if meeting_node is None:
            return None

        # The distance from the head to the entry is congruent, modulo the
        # cycle length, to the distance from the meeting node to the entry.
        pointer_from_head = head
        pointer_from_meeting = meeting_node

        while pointer_from_head is not pointer_from_meeting:
            # A meeting node proves that both references remain non-null.
            pointer_from_head = pointer_from_head.next
            pointer_from_meeting = pointer_from_meeting.next

        return pointer_from_head

    @staticmethod
    def _find_meeting_node(head: ListNode | None) -> ListNode | None:
        """Return a node inside the cycle, or None for an acyclic list."""
        slow_pointer = head
        fast_pointer = head

        while fast_pointer is not None and fast_pointer.next is not None:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

            if slow_pointer is fast_pointer:
                return slow_pointer

        return None


class Solution:
    """LeetCode-compatible entry point."""

    def detectCycle(self, head: ListNode | None) -> ListNode | None:
        return CycleEntryFinder.find_entry(head)

Interview follow-ups

How would a hash-set solution work?

Walk from the head while storing each node object in a set. Before inserting a node, check whether it is already present. The first repeated object is the cycle entry: every node before the entry is reached only once, while the entry is the first node reached for a second time after a full trip around the loop.

This approach is also O(n) time under expected constant-time hashing and is often the easiest version to derive. Its tradeoff is O(n) auxiliary space, compared with Floyd’s O(1). The set must contain node identities rather than values because values need not be unique.

What if the interviewer asks only whether a cycle exists?

Run only Floyd’s first phase. Return True when the pointers meet and False when the fast pointer or its next link becomes None. A meeting can occur only if some node is reachable repeatedly, and the fast pointer cannot escape a reachable cycle, so those two outcomes cover every possible list.

The running time remains O(n) and the auxiliary space remains O(1), but there is no need to reset a pointer or perform the entry-finding phase. This is precisely the simpler Linked List Cycle problem.

How can the algorithm also return the cycle length?

After phase one finds a meeting node, keep one pointer fixed and move another pointer around the cycle until it returns to that node, counting edges. Every node on the simple cycle is encountered exactly once, so the count is the cycle length L. The entry can still be found using the normal second phase.

This adds at most one traversal of the cycle. The total time stays O(n) and the auxiliary space stays O(1). If both the entry distance and cycle length are required, count the phase-two steps as a while locating the entry.

How would the cycle be removed safely?

First find the entry without modifying anything. If there is no entry, return the original list unchanged. Otherwise, begin at the entry and walk around the cycle until reaching the unique cycle node whose next pointer is the entry; set that link to None.

That final node is the back-edge source, so removing exactly its outgoing edge preserves every reachable node and turns the structure into a conventional finite list. Detection plus removal takes O(n) time and O(1) space. The important tradeoff is mutation: it is valid only when the caller owns the list and explicitly permits changing it.

Can the entry be found by returning the phase-one meeting node?

Not in general. The meeting position depends on the length of the non-cyclic prefix and the cycle length, so it can be any node in the cycle. For example, changing only the prefix length changes where the faster pointer catches the slower one even though the cycle entry itself is unchanged.

The second phase converts that arbitrary meeting position into the entry using the distance congruence above. It costs up to O(n) additional pointer moves but no additional asymptotic time or space. A candidate who returns the first meeting node has solved cycle detection, not cycle-entry detection.

What changes if another thread can mutate the list during traversal?

Floyd’s proof assumes that every node’s next reference stays fixed for the duration of the operation. Concurrent rewiring can make the pointers observe incompatible versions of the structure, producing an incorrect result or even preventing termination.

A production implementation should traverse an immutable snapshot, use a lock that covers all relevant links, or rely on a data-structure-specific versioning protocol and retry when the version changes. Copying a snapshot costs O(n) time and space; locking preserves the algorithm’s O(1) auxiliary space but can block writers. Without one of those consistency guarantees, no complexity or correctness claim from the static-list algorithm is reliable.