Floyd's Cycle Detection -- Interview Preparation¶

Junior Questions (1-15)¶

Middle Questions (16-30)¶

Senior Questions (31-42)¶

Professional Questions (43-50)¶

Coding Challenge -- Linked List Cycle II (LeetCode 142)¶

Given the head of a linked list, return the node where the cycle begins, or null if there is no cycle.

Constraints: - 0 <= number of nodes <= 10^4 - Must use O(1) extra memory.

Tests: - [3, 2, 0, -4], cycle at index 1 -> node with value 2 - [1, 2], cycle at index 0 -> node with value 1 - [1], no cycle -> null - [] -> null - [1, 2, 3, 4, 5], no cycle -> null

Go¶

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

// DetectCycle returns the node where the cycle begins, or nil if none.
// Two-phase Floyd's:
//   Phase 1: tortoise-hare detection -> meeting point m, where m is inside the cycle.
//   Phase 2: reset one pointer to head; advance both 1 step; they meet at cycle entry.
// Correctness: from mu = k*lambda - m, walking mu steps from head and from meeting
// both land on the cycle entry node.
// Time: O(mu + lambda). Space: O(1).
func DetectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            // Phase 2.
            p := head
            for p != slow {
                p = p.Next
                slow = slow.Next
            }
            return p
        }
    }
    return nil
}

func main() {
    // [3, 2, 0, -4] with cycle at index 1
    n3 := &ListNode{Val: 3}
    n2 := &ListNode{Val: 2}
    n0 := &ListNode{Val: 0}
    nM4 := &ListNode{Val: -4}
    n3.Next = n2
    n2.Next = n0
    n0.Next = nM4
    nM4.Next = n2 // cycle back to n2

    start := DetectCycle(n3)
    if start != nil {
        fmt.Printf("Cycle starts at node with value %d\n", start.Val) // 2
    } else {
        fmt.Println("No cycle")
    }

    // No cycle
    a := &ListNode{Val: 1}
    b := &ListNode{Val: 2}
    a.Next = b
    fmt.Println(DetectCycle(a)) // <nil>
}

Java¶

public class LinkedListCycleII {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int v) { this.val = v; }
    }

    /**
     * Detect the cycle's entry node, or null if none.
     *
     * Phase 1: tortoise-hare detection (1 vs 2 steps).
     * Phase 2: reset one to head; advance both 1 step; meet at cycle start.
     *
     * Correctness rests on the identity mu = k*lambda - m, where mu = tail length,
     * lambda = cycle length, and m = meeting offset inside the cycle. From this,
     * walking mu steps from head and mu steps from the meeting point both
     * land on the cycle entry.
     *
     * Time: O(mu + lambda). Space: O(1).
     */
    public static ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        // [3, 2, 0, -4] with cycle at index 1
        ListNode n3 = new ListNode(3);
        ListNode n2 = new ListNode(2);
        ListNode n0 = new ListNode(0);
        ListNode nM4 = new ListNode(-4);
        n3.next = n2; n2.next = n0; n0.next = nM4; nM4.next = n2;

        ListNode start = detectCycle(n3);
        System.out.println(start == null ? "no cycle" : ("cycle at value " + start.val));
        // expected: cycle at value 2

        // No cycle
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        a.next = b;
        System.out.println(detectCycle(a)); // null
    }
}

Python¶

"""LeetCode 142 -- Linked List Cycle II.

Return the node where the cycle begins, or None if no cycle exists.
Constant extra memory.
"""

from typing import Optional


class ListNode:
    __slots__ = ("val", "next")

    def __init__(self, val: int = 0, nxt: "Optional[ListNode]" = None) -> None:
        self.val = val
        self.next = nxt


def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Two-phase Floyd's tortoise-and-hare:

    Phase 1 (detection): slow advances 1 step, fast advances 2 steps. If they
    meet at node m inside the cycle, a cycle exists.

    Phase 2 (cycle start): reset slow to head; advance both 1 step at a time.
    They meet at the cycle's entry.

    Correctness relies on mu = k*lambda - m where mu = tail length,
    lambda = cycle length, m = offset of meeting from cycle entry. After
    Phase 1 the hare has lapped the cycle k times; walking mu more steps from
    head and from the meeting point both land on the cycle entry.

    Time:  O(mu + lambda).
    Space: O(1).
    """
    if head is None:
        return None
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            p = head
            while p is not slow:
                p = p.next
                slow = slow.next
            return p
    return None


if __name__ == "__main__":
    # [3, 2, 0, -4] with cycle at index 1
    n3, n2, n0, nM4 = ListNode(3), ListNode(2), ListNode(0), ListNode(-4)
    n3.next = n2
    n2.next = n0
    n0.next = nM4
    nM4.next = n2

    start = detect_cycle(n3)
    print(f"cycle at value {start.val}" if start else "no cycle")  # 2

    # No cycle
    a, b = ListNode(1), ListNode(2)
    a.next = b
    print(detect_cycle(a))  # None

Whiteboard Walkthrough -- Find the Duplicate Number (LeetCode 287)¶

A classic follow-up that demonstrates Floyd's beyond linked lists.

Problem. Given an array nums of n + 1 integers where each integer is in [1, n], find the one duplicate. Constraints: O(1) extra memory; the array must not be modified.

Idea. Treat the array as a function f(i) = nums[i]. By the pigeonhole principle (n + 1 values mapping into n possible images), some pair i != j has nums[i] = nums[j]. The directed graph i -> nums[i] therefore has a cycle, and the cycle's entry point (the node with two incoming edges) is exactly the duplicate value.

For nums = [1, 3, 4, 2, 2]:
  f(0) = 1
  f(1) = 3
  f(3) = 2
  f(2) = 4
  f(4) = 2  <-- cycle entry; duplicate = 2

Go¶

func FindDuplicate(nums []int) int {
    slow, fast := nums[0], nums[0]
    // Phase 1
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }
    // Phase 2
    slow = nums[0]
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

Java¶

public static int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

Python¶

def find_duplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

This is one of the few production-rare problems where Floyd's is the only acceptable answer because the constraints rule out sorting (mutates) and a hash set (O(n) memory).

Mistakes Interviewers Watch For¶

How to Approach a New Floyd's Problem¶

A four-step recipe interviewers like to see verbalized:

1. Identify the iterated-function structure. "Can I define f(state) = next_state deterministically?" If yes, Floyd's is a candidate.
2. Decide whether you need detection only or also the cycle start. Detection is one phase; cycle start requires Phase 2.
3. Pick the right starting positions. Linked lists: slow = fast = head, then slow = slow.next; fast = fast.next.next. Function-on-arrays: slow = fast = nums[0], then do { slow = f(slow); fast = f(f(fast)) } while (slow != fast). The two styles differ by one iteration and the cycle-start formula adjusts accordingly.
4. Validate on edge cases. Empty input, single node, self-loop, cycle of length 1, cycle starting at head (mu = 0).

If you can verbalize these four steps before writing code, you will produce correct solutions and demonstrate clear thinking.

Quick-Recall Cheat Sheet¶

Mnemonic: Slow steps, Fast leaps, Meet means loop, Reset head finds start.

If you remember the table and the mnemonic, you can reconstruct any solution under interview pressure.