SyntaxPilot
Courses/DSA and Coding Problems/Lesson 22
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 22 of 90

Floyd's cycle detection and the cycle start

queued

These are the notes for DSA episode 22. Last episode, one missing line made a linked list loop back on itself, and printing it would never end. Today we detect such a cycle. The obvious way, a notebook of every node visited searched from the top, is O(n²) and times out on 4 lakh nodes. A HashSet makes it O(n) but costs O(n) memory. Floyd's tortoise and hare does it in O(n) time and O(1) space: a slow pointer moves one step, a fast pointer moves two, and on a loop the fast one must land on the slow one. Then, with one line of algebra (a = kL − b), we find where the loop starts. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A delivery boy gets his route as a chain of slips: at each house, the slip says which house to visit next. Normally the last slip says "done, go home". One day the slip at house 6 says "go to house 3". He walks 3, 4, 5, 6, 3, 4, 5, 6 ... all day, and every house looks like the next stop on the route. How would he notice? How would a program?

On the route In the code
A house A node
The slip "next address" next
"Done, go home" next == null
The wrong slip at house 6 the last node's next points to an earlier node
Going round and round a cycle: a walk "until null" never ends
The house the loop enters the cycle start

Problem statement

  1. Linked List Cycle: given head, return true if the list has a cycle.
  2. Linked List Cycle II: return the node where the cycle starts, or null if there is none.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> (back to 3)    →  true, starts at 3
1 -> 2 -> 3 -> 4 -> 5 -> null                 →  false

Edge cases: a loop back to the head, a single node pointing to itself, a single normal node, an empty list.

To make test lists we use build(pos, values...): the last node points back to the node at index pos, or to null when pos = -1.

    static Node build(int pos, int... a) {
        Node head = null, tail = null, loop = null;
        for (int i = 0; i < a.length; i++) {
            Node n = new Node(a[i]);
            if (head == null) head = n;
            else tail.next = n;
            tail = n;
            if (i == pos) loop = n;
        }
        if (tail != null) tail.next = loop;
        return head;
    }

Brute force: a notebook of visited nodes

Write every visited node in a notebook (an ArrayList). At each node, check the notebook from the top: seen it before? Cycle. Reached null? No cycle. Compare the node objects (same house), never their values (two houses can have the same name on the door).

    static boolean bruteCycle(Node head) {
        List<Node> seen = new ArrayList<>();
        for (Node c = head; c != null; c = c.next) {
            if (seen.contains(c)) return true;
            seen.add(c);
        }
        return false;
    }

bruteCycle(build(2, 1, 2, 3, 4, 5, 6)) printed true, and bruteCycle(build(-1, 1, 2, 3, 4, 5)) printed false.

The big input: 4 lakh nodes

        int n = 400000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = i + 1;
        Node head = build(n - 1, a);          // the last node points to itself
        long t0 = System.nanoTime();
        Object r = bruteCycle(head);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("answer = " + r + ", " + ms + " ms");

Result: Time Limit Exceeded (it needed about 18 seconds on our machine; the limit is 8).

Why the brute force is slow

ArrayList.contains reads the notebook from the top: the i-th node costs i checks, so the total is about n² / 2.

Nodes Checks (about n²/2)
1,000 5 lakh
40,000 80 crore
4,00,000 8 × 10¹⁰

Better: a HashSet (O(n) time, O(n) memory)

    static boolean hashCycle(Node head) {
        Set<Node> seen = new HashSet<>();
        for (Node c = head; c != null; c = c.next)
            if (!seen.add(c)) return true;
        return false;
    }

add returns false when the node is already in the set. On the same 4 lakh nodes: answer = true, 94 ms. Fast, but the notebook is still there: one entry per node, O(n) extra memory. The interviewer's follow-up is always: now do it in O(1) memory.

The key insight: a tortoise and a hare

Send two pointers from the head: slow moves 1 step, fast moves 2 steps.

On a running track In the list
A walker, one step at a time slow = slow.next
A runner, two steps at a time fast = fast.next.next
Straight road: the runner reaches the end first fast hits null: no cycle
Circular track: the runner laps the walker slow == fast: cycle

Why can't the hare jump over the tortoise? Once both are inside the loop, look at the gap from fast to slow going round. Each move, fast gains 2 and slow gains 1, so the gap shrinks by exactly 1: 4, 3, 2, 1, 0. It must hit 0. And it happens before slow completes one lap, so the whole thing is O(n).

Trace on 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> (3):

Move slow fast
start 1 1
1 2 3
2 3 5
3 4 3 (6, then round to 3)
4 5 5: they meet, cycle

The optimal solution in Java

public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }
    static Node build(int pos, int... a) {
        Node head = null, tail = null, loop = null;
        for (int i = 0; i < a.length; i++) {
            Node n = new Node(a[i]);
            if (head == null) head = n;
            else tail.next = n;
            tail = n;
            if (i == pos) loop = n;
        }
        if (tail != null) tail.next = loop;
        return head;
    }
    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println(hasCycle(build(2, 1, 2, 3, 4, 5, 6)));
        System.out.println(hasCycle(build(-1, 1, 2, 3, 4, 5)));
        System.out.println(hasCycle(build(0, 1, 2, 3)));
        System.out.println(hasCycle(build(0, 7)));
        System.out.println(hasCycle(build(-1, 7)));
        System.out.println(hasCycle(null));
    }
}

Output:

true
false
true
true
false
false

On the 4 lakh node list: answer = true, 3 ms, with just two pointers of memory. The loop condition checks fast != null and fast.next != null because fast takes two steps; it is also the "no cycle" exit.

Part 2: where does the loop start?

Name the distances:

  • a = steps from the head to the loop start,
  • b = steps from the loop start to the meeting point,
  • L = the loop length.

When they meet, slow has walked a + b. Fast walked twice as far, which is slow's distance plus some whole laps:

2(a + b) = a + b + kL      →      a + b = kL      →      a = kL − b

So from the meeting point, walking a more steps completes whole laps and lands exactly on the loop start. And a is also the distance from the head to the start. Reset one pointer to the head, move both one step at a time, and they meet at the start.

Check on our route: a = 2 (1 → 3), they met at 5 so b = 2 (3 → 5), L = 4: a = 4 − 2 = 2. ✓ Phase 2: p = 1, slow = 5 → p = 2, slow = 6 → p = 3, slow = 3. Meet at 3.

    static Node cycleStart(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                Node p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }
    static String at(Node n) {
        return n == null ? "no cycle" : "starts at " + n.val;
    }

With build(2, 1..6), build(0, 1, 2, 3), build(5, 1..6), build(0, 7) and build(-1, 1, 2, 3) it printed:

starts at 3
starts at 1
starts at 6
starts at 7
no cycle

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// the last node points back to the node at index pos (or to nullptr when pos == -1)
Node* build(int pos, const vector<int>& a) {
    Node *head = nullptr, *tail = nullptr, *loop = nullptr;
    for (int i = 0; i < (int)a.size(); i++) {
        Node* n = new Node(a[i]);
        if (!head) head = n; else tail->next = n;
        tail = n;
        if (i == pos) loop = n;
    }
    if (tail) tail->next = loop;
    return head;
}

bool hasCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Node* cycleStart(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            Node* p = head;
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;
        }
    }
    return nullptr;
}

int main() {
    cout << boolalpha << hasCycle(build(2, {1, 2, 3, 4, 5, 6})) << " " << hasCycle(build(-1, {1, 2, 3, 4, 5})) << "\n";
    Node* s = cycleStart(build(2, {1, 2, 3, 4, 5, 6}));
    cout << (s ? "starts at " + to_string(s->val) : string("no cycle")) << "\n";
    cout << (cycleStart(build(-1, {1, 2, 3})) ? "cycle" : "no cycle") << "\n";
}

Output:

true false
starts at 3
no cycle

The same solution in Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def build(pos, *a):
    head = tail = loop = None
    for i, x in enumerate(a):
        n = Node(x)
        if head is None: head = n
        else: tail.next = n
        tail = n
        if i == pos: loop = n
    if tail: tail.next = loop
    return head

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:          # 'is' compares nodes, not values
            return True
    return False

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        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

print(has_cycle(build(2, 1, 2, 3, 4, 5, 6)), has_cycle(build(-1, 1, 2, 3, 4, 5)))
s = cycle_start(build(2, 1, 2, 3, 4, 5, 6))
print("starts at", s.val if s else None)
print(cycle_start(build(-1, 1, 2, 3)))

Output:

True False
starts at 3
None

Three real bugs

Bug 1: while (fast.next != null)

On the straight list 1 -> 2 -> 3 -> 4:

Exception in thread "main" java.lang.NullPointerException: Cannot read field "next" because "<local2>" is null
    at Main.hasCycle(Main.java:21)
    at Main.main(Main.java:29)

Fast jumped from 3 straight to null, and then we read null.next. With an even number of nodes fast always lands on null. Check fast != null first, then fast.next != null.

Bug 2: comparing values, slow.val == fast.val

On the straight list 3 -> 3 -> 3 -> 3 it printed true. Wrong: slow and fast were different nodes holding the same number. Compare references: slow == fast (Python: slow is fast).

Bug 3: fast starting one step ahead (fast = head.next)

Detection still works, but phase 2 doesn't: the meeting point shifts by one, a = kL − b is off by one, and p and slow circle the loop one step apart forever. Result: Time Limit Exceeded. If you need the start, both pointers must begin at head.

Complexity

Approach Time Extra space 4 lakh nodes
Notebook in an ArrayList O(n²) O(n) Time Limit Exceeded
HashSet O(n) average O(n) 94 ms
Floyd: hasCycle O(n) O(1) 3 ms
Floyd: cycleStart O(n) (meet, then a more steps) O(1)

Common mistakes

Mistake What you see Why Fix
while (fast.next != null) NullPointerException fast can already be null fast != null && fast.next != null
if (slow.val == fast.val) true for 3 -> 3 -> 3 -> 3 -> null equal values, different nodes if (slow == fast)
fast = head.next, then phase 2 Time Limit Exceeded meeting point off by one slow = fast = head
Phase 2 moving one pointer by 2 wrong start or an endless loop a = kL − b needs equal speeds both move one step
Walking "until null" to print a list that may loop the program never ends a cycle has no null detect the cycle first
ArrayList as the notebook TLE on big input contains is O(n) HashSet, or better, Floyd

Mini project: is this playlist on repeat?

A music app stores each song's "next song". A user edited the queue and may have created a loop. Report "repeat from song X" or "plays to the end":

        Node queue = build(3, 10, 20, 30, 40, 50, 60);   // 60 goes back to 40
        Node s = cycleStart(queue);
        System.out.println(s == null ? "plays to the end" : "repeat from song " + s.val);

It printed repeat from song 40. Extension: also print how many songs are on repeat (practice 1).

Practice

  1. Length of the cycle.
Solution

After slow and fast meet, keep one pointer still and walk the other round the loop until it comes back.

    static int cycleLength(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                int len = 1;
                for (Node c = slow.next; c != slow; c = c.next) len++;
                return len;
            }
        }
        return 0;
    }

It printed 4 for build(2, 1..6), 0 for a straight list, and 1 for a single self loop.

  1. Happy number: repeatedly replace n by the sum of the squares of its digits. Is it "happy" (reaches 1)? The sequence either reaches 1 or loops, so use slow and fast on numbers.
Solution
    static int next(int n) {
        int s = 0;
        while (n > 0) { int d = n % 10; s += d * d; n /= 10; }
        return s;
    }
    static boolean isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = next(slow);
            fast = next(next(fast));
        } while (slow != fast);
        return slow == 1;
    }

isHappy(19) → true, isHappy(2) → false, isHappy(7) → true. (1 loops to itself, so they meet at 1 for happy numbers.)

  1. Find the duplicate number: an array of n + 1 numbers, each in 1..n, has exactly one repeated value. Find it in O(1) extra space without changing the array.
Solution

Treat i → a[i] as a next pointer. The duplicate value is where two indices point to the same place: the cycle start.

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

{1, 3, 4, 2, 2} → 2, {3, 1, 3, 4, 2} → 3.

  1. Middle node with the same two pointers: see episode 21's practice 2 (slow stops in the middle when fast reaches the end).

Quick quiz

// build(4, 1, 2, 3, 4, 5): node 5's next = node 5
System.out.println(hasCycle(build(4, 1, 2, 3, 4, 5)));
  • true
  • false
  • NullPointerException
  • it never stops
Answer

true. Position 4 is the last node, so node 5 points to itself: a loop of length 1. Fast gets stuck circling on 5 and slow walks into it. (Real output: true.)

Interview questions

  1. Detect a cycle in O(1) space. Floyd's slow (1 step) and fast (2 steps) pointers; they meet if and only if there is a cycle.
  2. Why do they always meet, and why can't fast skip over slow? Inside the loop the gap shrinks by exactly 1 per move.
  3. Find the start of the cycle and prove it. 2(a + b) = a + b + kL gives a = kL − b; reset one pointer to head and move both by 1.
  4. Find the length of the cycle. From the meeting point, walk until you return.
  5. Why not move fast by 3? Then the gap shrinks by 2 each move, so on an even-length loop with an odd starting gap it skips 0 every lap and they never meet. Speeds 1 and 2 shrink the gap by exactly 1, which guarantees a meeting, and the start-finding formula relies on fast being exactly twice as fast.
  6. HashSet vs Floyd? Both O(n) time; HashSet uses O(n) memory and is easier to extend (e.g. which node repeats first); Floyd uses O(1).
  7. Where else does Floyd appear? Happy numbers, finding the duplicate number, detecting loops in any "next state" function (random number generators, x → f(x)).
  8. What's the time to find the start? O(n): the first meeting happens within one lap of slow after it enters the loop; phase 2 takes a steps.

Glossary

Term Meaning
Cycle (in a linked list) Some node's next points back to an earlier node (or itself), so the list never reaches null
Cycle start The first node of the loop: the one two different next arrows point to
Self loop A node whose next is itself: a cycle of length 1
Tortoise and hare Floyd's two pointers: slow (1 step) and fast (2 steps)
Floyd's cycle detection Detecting a cycle with slow and fast pointers in O(n) time, O(1) space
Meeting point The node where slow and fast first coincide
a, b, L Head-to-start distance, start-to-meeting distance, loop length
Reference equality slow == fast in Java: the same object, not equal values
HashSet A set with O(1) average add/contains, built on hashing
ArrayList.contains Searches a list from the start: O(n)
Phase 2 Resetting one pointer to head and moving both by one to find the start
NullPointerException Java's error when you read a field of null
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)
O(1) space Extra memory that doesn't grow with the input (a few variables)

Summary

  • A cycle means some next points back; a walk "until null" never ends.
  • Notebook in an ArrayList: O(n²), times out on 4 lakh nodes. HashSet: O(n) time but O(n) memory.
  • Floyd: slow +1, fast +2. Loop while fast != null && fast.next != null; slow == fast means a cycle. O(n) time, O(1) space.
  • Cycle start: a = kL − b, so reset one pointer to head and move both by one; they meet at the start.
  • Compare nodes, not values; start both pointers at head.

Next episode: Merge k sorted lists with a heap.