Find Out if a Linked List has a Cycle – Tech Interview Dot Org

Without marking nodes, find out if a linked list has a cycle in it or not.

💡Strategies for Solving This Problem

Classic Problem, Elegant Solution

Got this at Amazon. It's a standard problem but the solution (Floyd's Cycle Detection) is so clever that when you see it, it clicks forever.

The Insight

Imagine two runners on a circular track. If one runs twice as fast, they'll eventually lap the slower runner. Same idea with pointers in a linked list.

Floyd's Algorithm (Tortoise and Hare)

Use two pointers: slow (moves 1 step) and fast (moves 2 steps)
If there's a cycle, fast will eventually catch up to slow
If there's no cycle, fast reaches the end (null)

This is O(n) time and O(1) space. You can't do better.

Alternative: Hash Set (Not Optimal)

Store visited nodes in a Set. If you see a node twice, there's a cycle. Works but uses O(n) space. My Amazon interviewer said "Can you do it without extra space?" - that's your cue for Floyd's.

Follow-Up Questions They'll Ask

"Where does the cycle begin?" - This is the hard part. After detecting a cycle, there's a mathematical proof about where the entry point is.
"What's the length of the cycle?" - Once pointers meet, count how many steps until they meet again.

I didn't know these follow-ups in my first Amazon interview. Study them.

✅Solution

Solution: Floyd's Cycle Detection

function hasCycle(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;          // Move 1 step
        fast = fast.next.next;     // Move 2 steps

        if (slow === fast) {
            return true;  // Cycle detected!
        }
    }

    return false;  // Fast reached end, no cycle
}

// Test with cycle
let node1 = { val: 1, next: null };
let node2 = { val: 2, next: null };
let node3 = { val: 3, next: null };
let node4 = { val: 4, next: null };

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;  // Creates cycle

console.log(hasCycle(node1));  // true

// Test without cycle
let listNoCycle = { val: 1, next: { val: 2, next: null } };
console.log(hasCycle(listNoCycle));  // false

Why This Works: The Math

Let's say the cycle length is C and slow has moved k steps into the cycle. When they meet:

Slow has traveled: n steps total
Fast has traveled: 2n steps (twice as fast)
The difference (n steps) must be a multiple of C

That means fast has lapped slow exactly enough times to meet. Math proof is complex, but the algorithm works.

Follow-Up: Find Cycle Start Point

function detectCycle(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;

    // Phase 1: Detect if cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            // Cycle detected!
            // Phase 2: Find start of cycle
            slow = head;

            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }

            return slow;  // This is the cycle start
        }
    }

    return null;  // No cycle
}

The Magic of Finding Cycle Start

When pointers meet, reset slow to head and move both at same speed. They'll meet at the cycle entry point.

I won't explain the full proof (takes 10 minutes), but here's the intuition: The distance from head to cycle start equals the distance from meeting point to cycle start (modulo cycle length).

My interviewer at Amazon asked me to prove this. I couldn't. Still got the offer because I knew the algorithm worked.

Complexity Analysis

Time: O(n) - In worst case, we visit each node at most twice
Space: O(1) - Only two pointer variables

Why O(n) time? Fast pointer moves at most 2n steps before either:

Reaching end (no cycle)
Catching slow pointer (cycle detected)