Two walkers on the same track at different speeds. If the track loops, the fast one laps the slow one, and that collision is a cycle detector using no memory at all.
Also called Floyd’s tortoise and hare. It answers a question that looks like it needs a hash set, have I been here before, using two pointers and nothing else. The interviewer is usually testing whether you can get from the O(n)-space answer to the O(1)-space answer.
next. An index i maps to nums[i]. A number maps to the sum of the squares of its digits. Any such function traces a path that must eventually repeat, and the question is about that repetition or about a position along the path.i → nums[i] is a next pointer and the array is a linked structure. Once you see that, “find the duplicate” becomes “find the start of the cycle”. Recognising this disguise is the single highest-value thing on this page.slow one step and fast two steps per iteration. If the path is finite and has no cycle, fast falls off the end and you are done. If there is a cycle, both pointers end up inside it, and since fast gains exactly one position on slow every iteration, the gap shrinks by one each time and must hit zero. They cannot jump past each other.Reading the figure. The straight run on the left is the tail, μ nodes long. The loop is the cycle, λ nodes long. M is where the two pointers meet. slow has walked μ + k steps and fast twice that, so μ + k is a whole number of laps.
Once both pointers are inside the cycle, let d be the number of positions fast is behind slow, measured going forward around the cycle. Each iteration fast advances 2 and slow advances 1, so d decreases by exactly 1, modulo the cycle length. It therefore reaches 0 within λ iterations. Because the change is exactly one per step, they cannot step over each other, which is why the speeds must be 1 and 2 and not, say, 1 and 3.
slow has taken μ + k steps for some k, and fast has taken 2(μ + k). Their difference, μ + k, must be a whole number of laps, so μ + k ≡ 0 (mod λ).
μ + k + μ steps in total, and since μ + k is a multiple of λ, that lands it exactly μ steps into the cycle too. They meet at the cycle start.This second phase is what turns cycle detection into cycle location, and it is the whole trick behind Find the Duplicate Number.
/// <summary>A singly linked list node. A class, not a record, so == means identity.</summary>
/// <example><c>new ListNode(1, new ListNode(2))</c> is the list 1 -> 2.</example>
public class ListNode(int val = 0, ListNode? next = null) // 0: a neutral default value
{
public int Val = val;
public ListNode? Next = next; // null: no next node, the list ends here
}
public static class CycleDetect
{
/// <summary>Return the meeting node if a cycle exists, else null.</summary>
/// <param name="head">First node, or null for an empty list.</param>
/// <returns>A node inside the cycle where slow and fast meet, or null.</returns>
/// <example>For 1 -> 2 -> 1 (a loop), <c>Detect(head)</c> returns a node in it.</example>
public static ListNode? Detect(ListNode? head)
{
ListNode? slow = head, fast = head; // both start at the head
// Invariant: fast has taken twice as many steps as slow.
// Checking fast and fast.Next first keeps the two-step move safe.
while (fast is not null && fast.Next is not null)
{
slow = slow!.Next; // 1 step. !: slow trails fast, so it is not null
fast = fast.Next.Next; // 2 steps
// In a cycle, fast gains 1 node per pass, so it must land on slow.
if (slow == fast) // class ==: same object, not same value
return slow;
}
return null; // fast ran off the end: no cycle
}
}
The guard fast is not null && fast.Next is not null covers both odd and even list lengths. Test fast before you read fast.Next. The ! on slow!.Next tells the compiler what the guard already proves: slow trails fast, so it is never null there.
public static class CycleLocate
{
/// <summary>Return the first node of the cycle, or null if there is none.</summary>
/// <param name="head">First node, or null.</param>
/// <returns>The node where the tail joins the cycle, or null.</returns>
/// <example>For 3 -> 2 -> 0 -> -4 -> back to 2, <c>CycleStart(head).Val</c> is 2.</example>
public static ListNode? CycleStart(ListNode? head)
{
ListNode? meeting = CycleDetect.Detect(head);
if (meeting is null)
return null; // no cycle, so no start node
// The head and the meeting point sit the same distance from the cycle start.
// So two pointers that move at the same speed meet exactly there.
ListNode walker = head!; // !: a cycle exists, so head is not null
// Invariant: walker and meeting are the same distance from the cycle start.
while (walker != meeting) // both move one step at a time
{
walker = walker.Next!; // !: inside a rho path every node has a Next
meeting = meeting.Next!;
}
return walker;
}
}
Reading the figure. Amber nodes are where the two pointers start phase 2. Green S is the cycle start, where they meet. Count the arrows: three from h to S, and three from M forward to S.
fast.Next.Next without checking fast.Next. On an even-length list this throws NullReferenceException. The two-part guard is not optional.record. For nodes you want identity. On a plain class, == compares references, which is right. A record overrides == to compare values, so two different nodes holding the same value look equal. Use ReferenceEquals(slow, fast) if you are unsure.slow == fast before moving. They start equal, so the check must come after the moves, or you report a cycle immediately.while (fast is not null && fast.Next is not null) gives the second middle. Read the problem statement for which one it wants.Given the head of a linked list, return true if the list has a cycle in it. Solve it with O(1) extra memory.
HashSet<ListNode> of visited nodes: O(n) time, O(n) space. A class hashes by reference by default, so this works as is. Say this first, then improve it. Interviewers like seeing the baseline named before it is beaten.fast ever reaches null, the list ends and there is no cycle. If there is a cycle, fast never escapes it, and it closes the gap on slow by one per step.public static class LinkedListCycle
{
/// <summary>Return true if the linked list contains a cycle.</summary>
/// <param name="head">First node, or null for an empty list.</param>
/// <returns>True if following Next repeats a node forever.</returns>
/// <example>For 3 -> 2 -> 0 -> -4 -> back to 2, <c>HasCycle(head)</c> returns true.</example>
public static bool HasCycle(ListNode? head)
{
ListNode? slow = head, fast = head; // both start at the head
// Invariant: fast has taken twice as many steps as slow.
// Checking fast and fast.Next first keeps the two-step move safe.
while (fast is not null && fast.Next is not null)
{
slow = slow!.Next; // 1 step. !: slow trails fast, so it is not null
fast = fast.Next.Next; // 2 steps: gains 1 node on slow per pass
if (slow == fast) // identity: same object
return true;
}
return false; // fast hit the end, so the list has no loop
}
}
List 3 → 2 → 0 → -4 with -4 pointing back to 2:
slow at 3, fast at 3.slow at 2, fast at 0.slow at 0, fast at 2.slow at -4, fast at -4. They meet.Reading the figure. Each panel is one turn. Amber nodes hold slow or fast. The curved arrow is the link from −4 back to 2 that makes the cycle. Green is the meeting node.
They meet at -4, so the answer is true.
Time bound: slow takes at most μ steps to enter the cycle, then at most λ more before fast catches it, so at most μ + λ ≤ n iterations.
false.Next = null: same.fast.Next is the node. One iteration puts both on it, so it returns true.Return the middle node of a singly linked list. If there are two middles, return the second one.
n / 2 nodes (integer division in C#). Correct but two traversals.fast has covered the whole list at double speed, slow has covered exactly half of it. No length needed, and it works on a stream you can only read once.public static class MiddleOfList
{
/// <summary>Return the middle node. The second middle if the length is even.</summary>
/// <param name="head">First node, or null.</param>
/// <returns>The middle node, or null for an empty list.</returns>
/// <example>For 1 -> 2 -> 3 -> 4 -> 5, <c>MiddleNode(head).Val</c> is 3.</example>
public static ListNode? MiddleNode(ListNode? head)
{
ListNode? slow = head, fast = head; // both start at the head
// Invariant: fast has taken twice as many steps as slow.
// So when fast reaches the end, slow is halfway.
while (fast is not null && fast.Next is not null)
{
slow = slow!.Next; // 1 step. !: slow trails fast, so it is not null
fast = fast.Next.Next; // 2 steps
// Even length: fast ends at null, which leaves slow on the second middle.
}
return slow;
}
}
while (fast is not null && fast.Next is not null)
while (fast.Next is not null && fast.Next.Next is not null)
The second variant needs a non-empty list, so guard head first. For a list of length 4 the first gives node 3 and the second gives node 2.
List 1 → 2 → 3 → 4 → 5. After two iterations slow is at 3 and fast is at 5, whose Next is null, so the loop stops. Answer 3. For 1 → 2 → 3 → 4, slow ends at 3, the second middle.
Reading the figure. Amber cells hold slow or fast. Green is the node returned. In the last row fast has run off the end, so it has no cell.
Start with a positive integer. Replace it by the sum of the squares of its digits, and repeat. The number is happy if this eventually reaches 1. Otherwise it loops forever without reaching 1. Return whether n is happy.
value → sum of squared digits. That is all the pattern needs.3 × 9² = 243, so the sequence is eventually trapped below 243 and cannot run away. A finite state space with a deterministic successor always ends in a cycle.1 is a fixed point, 1 → 1. So “happy” is exactly “the cycle you land in is the one containing 1”. Run the tortoise and hare and check where they end up.public static class HappyNumber
{
/// <summary>Return true if repeatedly summing squared digits reaches 1.</summary>
/// <param name="n">A positive integer.</param>
/// <returns>True if n is a happy number.</returns>
/// <example><c>IsHappy(19)</c> returns true.</example>
public static bool IsHappy(int n)
{
// The sequence n, next(n), ... is a linked list of numbers.
// It either hits 1 and stays there, or loops. Floyd tells the two apart.
int slow = n, fast = NextValue(n); // fast starts 1 step ahead so the loop can run
// Stop on success (fast reaches the 1 fixed point) or on a collision.
// 1: NextValue(1) == 1, so 1 is a loop of length one.
while (fast != 1 && slow != fast)
{
slow = NextValue(slow); // 1 step
fast = NextValue(NextValue(fast)); // 2 steps
}
return fast == 1; // 1: we stopped because we reached 1
}
/// <summary>Sum of the squares of the decimal digits of value.</summary>
/// <param name="value">A non-negative integer.</param>
/// <returns>The digit-square sum.</returns>
/// <example><c>NextValue(19)</c> returns 82.</example>
public static int NextValue(int value)
{
int total = 0; // 0: empty sum
// Invariant: total holds the squares of the digits already peeled off.
while (value > 0) // 0: no digits left
{
int digit = value % 10; // % 10: base ten, so this is the last digit
value /= 10; // / 10: drop that digit
total += digit * digit; // digit squared
}
return total;
}
}
n = 19. The sequence is 19, 82, 68, 100, 1.
slow = 19, fast = 82.slow = 82, fast = 100. Fast took two steps.slow = 68, fast = 1. The loop exits. Happy.Reading the figure. Each arrow is one call to NextValue. Amber cells hold slow or fast. Green 1 means happy. The red ring is the cycle that 2 falls into, where the pointers would meet without ever seeing 1.
For n = 2 the sequence enters the cycle 4, 16, 37, 58, 89, 145, 42, 20, 4, the pointers collide inside it, and the answer is false.
The first NextValue call is O(log n) in the number of digits and collapses n to at most 243 immediately, after which the work is bounded by a constant.
n = 1: fast starts at NextValue(1) == 1. The loop never runs, so it returns true.n = 7: happy, via a longer path. Good sanity check.HashSet<int> solution is O(1) space too, because the state space is bounded by 243. Mention it. It is a fair answer and shows you know the bound.n: digit squares stay small, so int never overflows here. int.MaxValue maps to at most 10 × 81 = 810.An array nums of n + 1 integers holds values in the range 1..n. Exactly one value is repeated, possibly many times. Find it, without modifying the array and using O(1) extra space.
m, count how many values are ≤ m. If that count exceeds m, the duplicate is at or below m. That is O(n log n) time and O(1) space, and it is easier to derive under pressure. Have it as your backup.i → nums[i]. Values are in 1..n and indices in 0..n, so every value is a valid index and the walk never leaves the array.0. Index 0 is never a value, since values start at 1, so nothing points back into the start and the path has a genuine tail. That guarantees the rho shape rather than a pure loop.public static class FindDuplicate
{
/// <summary>Find the one repeated value in nums, read-only and in O(1) space.
/// Treats nums as a functional graph i -> nums[i]. The repeated value is the
/// entrance of the cycle that walk falls into.</summary>
/// <param name="nums">n + 1 integers, each in 1..n, with exactly one value repeated.</param>
/// <returns>The repeated value.</returns>
/// <example><c>Find([1, 3, 4, 2, 2])</c> returns 2.</example>
public static int Find(int[] nums)
{
// Phase 1: find a meeting point inside the cycle.
// nums[0]: index 0 is the start. No value is 0, so nothing points back to it.
int slow = nums[0], fast = nums[0];
// Invariant: fast has taken twice as many steps as slow.
// do-while: move first, because the pointers start equal.
do
{
slow = nums[slow]; // 1 step
fast = nums[nums[fast]]; // 2 steps
} while (slow != fast); // a cycle always exists, so this ends
// Phase 2: walk one pointer from the start. They meet at the entrance.
// Same trick as CycleStart: equal distances to the entrance.
int finder = nums[0]; // nums[0]: one step from the start, like slow
// Invariant: finder and slow are the same distance from the entrance.
while (finder != slow)
{
finder = nums[finder]; // 1 step
slow = nums[slow]; // 1 step
}
return finder;
}
}
nums = [1, 3, 4, 2, 2]. The walk from index 0 is 0 → 1 → 3 → 2 → 4 → 2 → 4 → …, a tail of 0, 1, 3 feeding the cycle 2, 4. Two arrows point at node 2, from index 3 and from index 4, and those are the two positions holding the value 2.
slow = 1, fast = 1.slow = 3, fast = 2.slow = 2, fast = 2. They meet.slow = 2, finder = 1.slow = 4, finder = 3.slow = 2, finder = 2. The answer is 2.Reading the figure. Green cells hold the repeated value, and green node 2 is the answer. Two arrows enter it: from index 3 and from index 4. Violet node 4 is the rest of the cycle. The text on the right lists where each pointer sits after each step.
They meet at 2, the answer.
[2, 2, 2, 2, 2]: still one cycle entrance, still correct. This is exactly what breaks the sum-formula trick.[1, 1]: n = 1, the walk is 0 → 1 → 1, answer 1.0 is a safe start: no value equals 0, so node 0 has in-degree zero and can never be inside the cycle.do-while shape matters. Phase 1 must move before comparing. The pointers start equal, so a top-tested while (slow != fast) would exit at once. C# has a real do { ... } while (slow != fast); loop, which says this exactly. Python needs while True with a break for the same thing.nums is a next pointer and the array is a linked list. Two indices holding the same value are two arrows into one node, which is a cycle entrance, so the duplicate is exactly the cycle start.”μ + k ≡ 0 (mod λ). Be able to write that line.fast is not null && fast.Next is not null. Compare nodes by reference, and keep ListNode a class, not a record.Pattern 4, Merge Intervals, leaves pointers behind. It is the first pattern where the whole insight is what to sort by, and where a greedy sweep replaces a search.