cf.completefrontend
LINKED LISTS · CORE

Floyd's cycle detection

Find out whether following links ever loops back, and where the loop starts, using a fast and a slow pointer and no extra memory.

Time O(n)Space O(1)4 practice problemsStep-through picture

The idea

Sometimes a chain of links loops back: the last node's next points to a node you already passed, so a walk along the chain never ends. This is called a cycle. A simple check remembers every node in a set and stops when it sees one twice, but the set can grow as big as the list.

Floyd's method, also called the tortoise and hare, uses two pointers instead. slow moves one node per step and fast moves two. If there is no cycle, fast reaches the end. If there is a cycle, both pointers end up going round the loop, and fast gains one node on slow every step, so it must land on slow after a while.

A second phase finds where the loop starts: put a new pointer, finder, at the head and move it and slow one node at a time. They meet exactly at the first node of the loop.

An everyday example

Two runners on a track shaped like the number 6

A path leads from the park gate onto a circular track. Two runners start at the gate, one twice as fast as the other. If the path had a dead end, the fast runner would reach it and stop. But the path joins a circle, so both runners end up lapping it, and since the fast one gains a little every second, it eventually catches up with the slow one from behind.

How the example maps to the code
In the exampleIn the code
The park gatehead
The circular trackthe cycle
The slow runnerslow = slow.next
The fast runnerfast = fast.next.next
The fast runner catches the slow oneslow === fast

From the slow way to floyd's cycle detection

  1. Start with the obvious way to notice a loop: remember every node you visit in a Set, and stop when you meet a node that is already in it. It works and even finds the loop's start, which is the first repeat. But the set grows with every node, so it needs O(n) extra memory.
  2. Without memory, you need a different signal. Here is one: a walker inside a loop can never leave it. If two walkers move at different speeds and both end up in the loop, the faster one keeps gaining on the slower one, like runners lapping a track. If there is no loop, the faster one simply reaches the end.
  3. So move slow one node and fast two nodes per step. Inside the loop, the distance from fast back to slow shrinks by exactly one each step, so it can't skip past zero: they must land on the same node. That answers "is there a cycle?" with two pointers. But the meeting node is usually not where the loop starts.
  4. A little counting fixes that. When they meet, slow has taken a number of steps that is a whole number of laps of the loop. So a new pointer, finder, starting at the head, and slow, starting from the meeting node, reach the loop's first node at the same moment if both move one step at a time. That two-phase loop is Floyd's cycle detection.

How it works

  1. Start slow and fast at head.
  2. While fast and fast.next exist, move slow one node and fast two nodes.
  3. If fast reaches the end, there is no cycle: return null.
  4. If slow === fast, they met inside the cycle.
  5. Put finder at head. Move finder and slow one node at a time until they are the same node.
  6. That node is where the cycle starts: return it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function findCycleStart(head) {
  2. let slow = head;
  3. let fast = head;
  4. while (fast !== null && fast.next !== null) {
  5. slow = slow.next;
  6. fast = fast.next.next;
  7. if (slow === fast) {
  8. let finder = head;
  9. while (finder !== slow) {
  10. finder = finder.next;
  11. slow = slow.next;
  12. }
  13. return finder;
  14. }
  15. }
  16. return null;
  17. }

How fast it is

TimeO(n)
Extra memoryO(1)

Before meeting, slow takes fewer than n steps, because fast catches it within one lap of the loop. The second phase takes at most n more steps. Only three pointers are kept, unlike a visited set that stores every node.

  • Best caseO(n)

    No cycle at all: fast falls off the end after about n / 2 loops and phase two never runs.

  • Average caseO(n)

    A cycle somewhere in the middle: phase one takes at most a + c steps, which is at most n, and phase two takes a more.

  • Worst caseO(n)

    A long path into a tiny loop, such as the last node linking to itself. On 10 nodes, phase one takes 9 steps and phase two takes 9 more, still under 2n in total.

Common mistakes

  • Comparing values (slow.val === fast.val) instead of nodes. Different nodes can hold equal values, which gives false cycles.
  • Checking slow === fast before moving them. They both start at head, so the check is true right away.
  • Moving finder and slow at different speeds in phase two. Both must move exactly one node per step.
  • Starting finder at the meeting point and slow at the head, then moving only one of them. Start one at the head, keep the other at the meeting point, and move both.

When to use it

Look for these clues in a problem:

  • The question asks whether following next links, redirects, or "go to" rules ever repeats.
  • Each item points to exactly one next item, like an array where nums[i] tells you where to go next.
  • The task asks for the first item that is part of a loop.
  • The task asks for O(1) extra space, so a set of visited nodes isn't allowed.

Check yourself

Answer each one in your head first, then open it.

Why compare nodes with === instead of comparing val?

Two different nodes can hold the same value. Only the same node object means the pointers really met, so comparing values can report a cycle that isn't there.

Why must slow and fast move before the first comparison?

They both start at head, so comparing first would say they met at once. The code moves them and then checks.

If the path before the loop has 5 nodes, how many steps does phase two take?

Exactly 5. finder needs 5 steps to reach the loop's first node, and slow arrives there at the same moment.

Can phase one take more than n steps?

No. slow enters the loop after a steps and is caught within c more, and a + c is the number of nodes, n.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

If there is no cycle, fast reaches the end and the function returns null, which is right. If there is a cycle, call the path before it a nodes long and the loop c nodes long. slow enters the loop after a steps, and fast is already inside. From then on, the distance from fast forward to slow around the loop drops by exactly one per step, so they meet within at most c more steps.

At the meeting, slow has taken s steps and fast has taken 2s, from the same start. The extra s steps that fast took were spent going round the loop, so s is a whole number of laps: a multiple of c. In the trace, s = 4 and c = 4.

Now finder starts at the head and slow at the meeting node, and both move one step at a time. After a steps, finder is at the loop's first node. slow has then taken s + a steps from the head in total: a steps to reach the loop, plus whole laps. So it is at the loop's first node too.

They can't meet earlier. Before a steps, finder is still on the path outside the loop, while slow is always inside it, so they are on different nodes. The first node they share is the loop's start, which is what the function returns.

Going deeper

3 more ideas

Why the two pointers must meet

Once both pointers are inside the loop, think of the distance from slow forward to fast around the loop. Each step slow moves one node and fast moves two, so that distance shrinks by exactly one. It can't jump over zero, so after at most one lap it becomes zero and they stand on the same node.

Why the second walk finds the start

Say the path before the loop has a nodes and the loop has c nodes. When they meet, slow has taken s steps and fast has taken 2s. The extra s steps were whole laps for fast, so s is a multiple of c. Now finder starts at the head and slow at the meeting point, and both move one node at a time. After a steps finder reaches the loop's start. slow has then taken s + a steps from the head in total, which is a steps plus whole laps, so it is also at the loop's start. They meet there for the first time.

It works on arrays too

If next[i] gives the index of the item after item i, the array is a linked list in disguise. Use indexes as the pointers: slow = next[slow] and fast = next[next[fast]]. This finds a repeated number in an array of n + 1 values from 1 to n, and it detects loops in any "go to the next state" rule, such as repeatedly summing the squares of a number's digits.

Work it by hand

Every step in a table, with why

A six-node list whose last node links back to the third. The path before the loop has 2 nodes and the loop has 4.

head = 8 -> 15 -> 4 -> 23 -> 16 -> 42, and 42.next = 4

StepPhaseslowfastfinderWhat happensWhy
1188-Both start at headNo check yet: they are equal at the start, so the code moves them before comparing.
21154-slow !== fastfast jumped 8 -> 15 -> 4 and is already inside the loop. slow is still on the path before it.
31416-slow !== fastslow enters the loop at 4. fast is two nodes ahead of it, which means it is two nodes behind it going round the loop of 4.
41234-slow !== fastfast went 16 -> 42 -> 4, wrapping round the loop. It is now one node behind slow.
511616-slow === fast: meetThe gap closed to zero. slow took 4 steps, exactly one lap of the 4-node loop.
6216168finder starts at headPhase two: finder goes to the head, slow stays at the meeting node, and fast is no longer used.
72421615finder !== slowBoth move one node. finder is still on the path; slow is going round the loop.
824164finder === slow: returnAfter 2 steps, the length of the path before the loop, finder arrives at 4, and so does slow.

It returns the node 4, where the loop starts, after 4 steps in phase one and 2 in phase two. No set was needed: the whole search kept three pointers.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Floyd's cycle detectionO(n)O(1)You must find a loop without extra memory, or without changing the nodes.
Set of visited nodesO(n)O(n)Memory is not a concern and you want the simplest code. The first node seen twice is the loop's start.
Mark visited nodes in placeO(n)O(1)You are allowed to change the nodes, for example by setting a seen flag on each, and to clean up after.

Extra memory: O(1): three pointers, slow, fast, and finder, compared with O(n) for a set of visited nodes.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Floyd's cycle detection and the other approaches, on a scale where each line up is 10 times more steps.
  • Floyd's cycle detection, Set of visited nodes, Mark visited nodes in place O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Floyd's cycle detection101,0001 million
Set of visited nodes101,0001 million
Mark visited nodes in place101,0001 million

Inputs that need care

5 tricky inputs
An empty list: head = null
fast !== null fails at once, so the loop never runs and the function returns null: no cycle.
One node that links to itself
After one step slow and fast are both that node, so they meet. finder starts at the head, which is already slow, so phase two takes zero steps and returns the head.
The whole list is the loop: the last node links to the head
With a = 0, they meet after exactly c steps, back at the head, and phase two takes zero steps. The answer is the head. On a five-node ring, phase one takes 5 steps.
Repeated values, like 5 -> 5 -> 5 with no cycle
The code compares nodes with ===, not values, so equal values never cause a false meeting. It correctly returns null.
An array where next[i] is the index to visit next
Use indexes as pointers: slow = next[slow] and fast = next[next[fast]]. Every index must point inside the array, or the walk reads undefined.

Variations and follow-ups

Twists interviewers add

Only ask whether a cycle exists

Stop at the first slow === fast and return true, or return false when fast reaches the end. Phase two is only needed when you want the loop's first node.

Measure the loop's length

After the meeting, keep fast still and move slow one node at a time, counting, until it comes back to fast. The count is c, the number of nodes in the loop.

Find the repeated number in an array

An array of n + 1 numbers, each from 1 to n, can be read as links: from index i go to index nums[i]. A repeated number means two indexes link to the same place, which is a loop's start. Floyd's method finds it in O(n) time without changing the array or using extra memory.

Brent's method

Instead of moving both pointers every step, keep one fixed and move the other, and teleport the fixed one forward whenever the step count hits a power of two. It finds the loop's length and start with fewer calls to next, which helps when computing the next item is expensive.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "does it ever loop?", "find where the cycle begins", or "an array where each value points to an index", especially with "O(1) extra space" or "don't change the input".
  • Explain phase one with the shrinking gap: "inside the loop, fast gains exactly one node on slow per step, so it can't jump over it." That one sentence answers "why must they meet?".
  • Explain phase two with laps: "slow has taken a whole number of laps when they meet, so after a more steps it is at the loop's start, the same place finder reaches after a steps from the head."
  • Test by hand on a list with no cycle, a one-node self loop, and a list whose loop starts at the head. They cover the null return and the zero-step phase two.
  • Expect the follow-up "why not move fast three steps at a time?". It still finds a cycle, but the gap shrinks by two per step, so it can jump past zero and need extra laps before the pointers land on the same node. The phase-two math also assumes fast took exactly twice as many steps as slow.

Where frontend code uses it

The same idea in real UI code
  • A router or CDN config can redirect /a to /b and /b back to /a. Following each rule to its next one is a linked chain, and a cycle check stops an infinite redirect loop.
  • When you walk up a chain of parent links, such as parentNode in a hand-built tree or a nested comment's parentId, bad data can make the chain loop. Cycle detection lets the code stop instead of freezing the tab.
  • Bundlers report circular imports (file a imports b, which imports a). When each module has one import to follow, the check is exactly this; with many imports it becomes graph cycle detection.

Related algorithms