Fast and Slow Pointers

Fast and slow pointers are a structural probe. One pointer moves one step at a time; the other moves two. If the list has a cycle, the faster pointer eventually laps the slower pointer. If there is no cycle, the fast pointer reaches null.

The Speed-Difference Invariant

The algorithm works because the distance between fast and slow changes predictably. Inside a cycle, fast gains one node per iteration relative to slow. It cannot keep missing forever; eventually both references point to the same node.

Scenario: Corrupted Retry Chain

A workflow engine stores retry steps as linked next references. A bug accidentally points a failed step back to an earlier step. A naive traversal never ends. Fast/slow detection lets the system reject the corrupted chain before a worker spins forever.

Same Pattern in Java, Python, and JavaScript

Cycle detection is the canonical fast/slow problem. The null checks protect the fast pointer before reading fast.next.

class ListNode { int value; ListNode next; }

class CycleDetection {
    static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

Edge Cases That Matter

• Empty list: fast is null immediately.
• Single node without cycle: fast.next is null.
• Single node pointing to itself: fast and slow meet after one iteration.
• Two-node cycle: meeting still happens.
• Very long acyclic list: fast exits without extra memory.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return whether a linked list contains a cycle.
• Return the middle node of a linked list.
• Return the node where a linked-list cycle begins, or null if no cycle exists.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class ListNode { int value; ListNode next; }

class HasCycle {
    static boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

class MiddleNode { static ListNode middle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } }

class CycleStart { static ListNode detect(ListNode head) { 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; } }

Solved modelWorked Interview Answer

Detect whether a linked list contains a cycle. Move slow one step and fast two steps. If they meet, a cycle exists; if fast reaches null, the list ends.

class ListNode { int value; ListNode next; }

class HasCycle {
    static boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Reading fast.next without checking fast first.
• Comparing node values instead of node identity.
• Forgetting single-node self-cycle behavior.
• Using a set when O(1) memory is explicitly required.
• Not explaining why fast eventually catches slow inside a cycle.

Execution guardrailQuick-Start Checklist

• Initialize slow and fast at head.
• Guard fast and fast.next.
• Move slow one step and fast two steps.
• Compare references, not values.
• State O(n) time and O(1) memory.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice linked-list cycle, cycle start, happy number, and middle node.
• Review tortoise-and-hare proof sketches.
• Compare set-based detection with O(1)-space detection.