Find a linked-list cycle by identity

Clarify the observable contract

The input is a singly linked node graph whose links remain unchanged while searching. A cycle means revisiting the same node object, not seeing the same integer value twice. Return the entry node or null for an acyclic or empty list. The sample deliberately gives two different nodes the value seven so a value-based shortcut would be visibly unsafe.

Use names such as a, b and c for node identities while tracing, because two printed sevens cannot identify the entry. A return type containing only the stored integer would be unable to express which equal-valued node participates in the loop. That limitation is independent of the detection algorithm chosen.

Walk through the verified program

The first node leads to a second seven and then nine, whose Next returns to that second node. Slow advances once and fast twice until they meet. Moving one cursor from the head and the meeting cursor one link at a time finds the shared entry. A separate two-node list with equal values remains acyclic, and null input returns null.

Once a meeting exists, the distance from the head to the entry and the meeting offset around the cycle align modulo the cycle length. Advancing both cursors one step preserves that alignment until they meet at the entry. Explain the distance relation rather than treating the reset-to-head step as a memorized trick.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var a = new Node(7); var b = new Node(7); var c = new Node(9); a.Next = b; b.Next = c; c.Next = b;
Console.WriteLine("entry:" + (Entry(a)?.Value.ToString(CultureInfo.InvariantCulture) ?? "none"));
Console.WriteLine("acyclic:" + (Entry(new Node(7) { Next = new Node(7) }) is null).ToString().ToLowerInvariant());
Console.WriteLine("empty:" + (Entry(null) is null).ToString().ToLowerInvariant());
static Node? Entry(Node? head) {
    Node? slow = head, fast = head;
    while (fast?.Next is not null) {
        slow = slow!.Next; fast = fast.Next.Next;
        if (ReferenceEquals(slow, fast)) { Node? cursor = head; while (!ReferenceEquals(cursor, slow)) { cursor = cursor!.Next; slow = slow!.Next; } return cursor; }
    }
    return null;
}
sealed class Node(int value) { public int Value { get; } = value; public Node? Next { get; set; } }

Account for time, storage and allocations

With an unchanged finite reachable structure, the algorithm uses O(n) pointer advances and O(1) auxiliary references. A visited-node set is a valid alternative with O(n) storage and often a simpler first explanation. Returning only Value loses identity information when several nodes share a value.

The reachable structure can be described by a finite stem length and a cycle length. Each phase advances only a linear number of links in their sum. The set-based alternative spends memory remembering identities but can reveal the repeated node directly, which may be a reasonable clarity tradeoff under a bounded input size.

Review assumptions and likely defects

Overriding value equality on a node type can make == or an ordinary equality-based set unsuitable for identity detection. ReferenceEquals states the contract directly. Concurrent link mutation invalidates the usual proof, and this sample provides neither synchronization nor a snapshot of a shared list.

Null checks must guard the fast cursor before its two-link advance. A one-node acyclic list and a self-loop exercise opposite outcomes with almost identical data. If a custom node overloads equality, ReferenceEquals continues to ask the object-identity question required by the proof.

Practice one: discriminate edge cases

Add a self-loop and a cycle whose entry is the head. Hint: test the returned object with ReferenceEquals rather than checking its Value. Keep a repeated-value acyclic fixture to catch accidental equality-based detection.

Add assertions about the exact returned reference for every cyclic fixture. For acyclic fixtures, compare with null. Do not derive an expected entry by running the same fast-and-slow procedure in the test; construct the expected node first and then wire the fixture around that known identity.

Practice two: defend an extension

Compare the constant-space solution with an identity-based visited set during an interview. Explain the proof burden and memory tradeoff, then define whether a production caller can mutate links during inspection and how ownership would enforce that rule.

For a concurrently maintained list, the most straightforward contract is that the caller owns an immutable snapshot or holds the required structural lock during inspection. A visited set alone does not repair concurrent rewiring. The senior tradeoff is therefore not just memory versus speed, but whether a stable graph exists to inspect.

Evaluate correctness and interview reasoning

A rigorous answer distinguishes repeated values from repeated nodes, supplies a termination argument for both acyclic and cyclic input, and explains why resetting one cursor locates the entry. It also recognizes that a set can be an acceptable initial solution when memory is available and clarity matters. The tested fixture intentionally hides identity behind duplicate displayed values, so output inspection alone is insufficient for richer tests. Demonstrate self-loop, head-entry and non-head-entry cases with reference assertions. These checks test the actual returned object, which is the central contract of this problem.