Find where a linked list loops back on itself

Distinguish detection from locating the entry

A baseline stores visited node identities. The first already-seen node is the entry, giving O(n) time and O(n) auxiliary space for n distinct reachable nodes. To eliminate that set, move slow one edge and fast two. If fast reaches None, the chain terminates. If a cycle exists, both eventually enter it, and their relative distance changes by one modulo its length each iteration, forcing a meeting. Compare with is: node values are irrelevant.

The first meeting is d, not entry b. Let the noncyclic prefix length be μ and cycle length be λ. At meeting, slow has walked t edges and fast 2t, so their distance difference t is a multiple of λ. The meeting's cycle offset is (t - μ) mod λ. Reset one pointer to head and leave the other at the meeting; move both one edge at a time. After μ steps the head pointer reaches entry, and the cycle pointer's offset becomes t modulo λ, which is zero. They cannot meet earlier when μ is positive because one pointer is outside the cycle.

This proves the second phase locates the first cyclic node. If μ is zero, the reset pointer may already equal the meeting and returns immediately. Both phases take O(μ + λ) time and O(1) auxiliary space; the acyclic case is O(n). The reference validates link types on every pointer step, preserving the same bound. It uses no recursion or visited set and never changes a link.

Follow-up 1: also return cycle length

Predict the minimal added state: start at the discovered entry, walk until that same object is reached again, and count edges. Take at least one step so a self-cycle has length one.

This adds O(λ) time and O(1) space. Returning every cycle node instead adds O(λ) output. Define the acyclic response as (None, 0) before coding.

Follow-up 2: safely break the cycle

Do not sever the entry's outgoing edge: that would make later cycle nodes unreachable from the head. Find the predecessor whose next is entry instead. Require exclusive mutation ownership; a concurrent writer can invalidate the proof or create a new cycle after repair. A senior candidate derives both phases and tests every entry position, not just a cycle at the head. A lead candidate separates read-only diagnosis from repair authorization, reports corruption, and defines how references held by other queue consumers remain valid.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/15-linked-list-cycle-entry
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    value: object
    next: "Node | None" = None

def _next(node):
    if node is None:
        return None
    if not isinstance(node, Node) or (node.next is not None and not isinstance(node.next, Node)):
        raise ValueError("links must be Node objects or None")
    return node.next

def cycle_entry(head):
    slow = fast = head
    while fast is not None:
        slow = _next(slow)
        fast = _next(_next(fast))
        if fast is not None and slow is fast:
            seeker = head
            while seeker is not slow:
                seeker = _next(seeker)
                slow = _next(slow)
            return seeker
    return None

import unittest
from solution import Node, cycle_entry

class CycleTests(unittest.TestCase):
    def test_every_small_prefix_and_cycle_length(self):
        self.assertIsNone(cycle_entry(None))
        for size in range(1, 25):
            for entry_index in range(-1, size):
                nodes = [Node(7) for _ in range(size)]
                for left, right in zip(nodes, nodes[1:]):
                    left.next = right
                if entry_index >= 0:
                    nodes[-1].next = nodes[entry_index]
                before = [node.next for node in nodes]
                expected = nodes[entry_index] if entry_index >= 0 else None
                self.assertIs(cycle_entry(nodes[0]), expected)
                self.assertTrue(all(node.next is link for node, link in zip(nodes, before)))

    def test_long_chain_and_invalid_links(self):
        head = None
        for _ in range(10000):
            head = Node(1, head)
        self.assertIsNone(cycle_entry(head))
        for bad in [42, "node", Node(1, 42)]:
            with self.assertRaises(ValueError):
                cycle_entry(bad)

if __name__ == "__main__":
    unittest.main()