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
- Linked List Cycle: given
head, returntrueif the list has a cycle. - Linked List Cycle II: return the node where the cycle starts, or
nullif 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
- 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.
- 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.)
- 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.
- Middle node with the same two pointers: see episode 21's practice 2 (
slowstops in the middle whenfastreaches 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)));
truefalseNullPointerException- 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
- 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.
- Why do they always meet, and why can't fast skip over slow? Inside the loop the gap shrinks by exactly 1 per move.
- Find the start of the cycle and prove it.
2(a + b) = a + b + kLgivesa = kL − b; reset one pointer to head and move both by 1. - Find the length of the cycle. From the meeting point, walk until you return.
- 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.
- 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).
- Where else does Floyd appear? Happy numbers, finding the duplicate number, detecting loops in any "next state" function (random number generators,
x → f(x)). - 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
asteps.
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
nextpoints 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 == fastmeans 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.