Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Move slow by one and fast by two. A cycle makes them meet; fast reaching the end proves none exists. When fast finishes, slow is in the middle.
If a list loops, a pointer moving two steps gains one step per move on a pointer moving one step, so inside the loop it must land on it. Without a loop, the fast pointer simply reaches the end. Floyd's second phase works because the distance from the head to the cycle's start equals the distance from the meeting point to the start, going round the loop.
Typical cost: O(n) time, O(1) space
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Linked List Cycle II
The problem statement, then the plan you would say out loud.
Return the node where the cycle begins, or null.
Plan before you code
- Find a meeting point with fast and slow.
- Reset one pointer to head.
- Move both one step at a time; they meet at the cycle start (distance maths).
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Detect a cycle
1type ListNode = { val: number; next: ListNode | null };2 3function hasCycle(head: ListNode | null): boolean {4 let slow = head, fast = head;5 while (fast && fast.next) {6 slow = slow!.next;7 fast = fast.next.next;8 if (slow === fast) return true;9 }10 return false;11}1class ListNode(val value: Int, var next: ListNode? = null)2 3fun hasCycle(head: ListNode?): Boolean {4 var slow = head5 var fast = head6 while (fast != null && fast.next != null) {7 slow = slow?.next8 fast = fast.next?.next9 if (slow === fast) return true10 }11 return false12}1class ListNode {2 int val;3 ListNode next;4 ListNode(int val) { this.val = val; }5}6 7static boolean hasCycle(ListNode head) {8 ListNode slow = head, fast = head;9 while (fast != null && fast.next != null) {10 slow = slow.next;11 fast = fast.next.next;12 if (slow == fast) return true;13 }14 return false;15}- Both pointers start at the head.
- Slow moves one step, fast moves two.
- If they ever meet, the list loops.
3.2Solution
Strict TypeScript, type-checked and tested.
Linked List Cycle II
1function detectCycle(head: ListNode | null): ListNode | null {2 let slow = head, fast = head;3 while (fast && fast.next) {4 slow = slow!.next;5 fast = fast.next.next;6 if (slow === fast) {7 let p = head;8 while (p !== slow) {9 p = p!.next;10 slow = slow!.next;11 }12 return p;13 }14 }15 return null;16}1fun detectCycle(head: ListNode?): ListNode? {2 var slow = head3 var fast = head4 while (fast != null && fast.next != null) {5 slow = slow?.next6 fast = fast.next?.next7 if (slow === fast) {8 var p = head9 while (p !== slow) {10 p = p?.next11 slow = slow?.next12 }13 return p14 }15 }16 return null17}1static ListNode detectCycle(ListNode head) {2 ListNode slow = head, fast = head;3 while (fast != null && fast.next != null) {4 slow = slow.next;5 fast = fast.next.next;6 if (slow == fast) {7 ListNode p = head;8 while (p != slow) {9 p = p.next;10 slow = slow.next;11 }12 return p;13 }14 }15 return null;16}Step by step
- Race: slow moves one step, fast moves two.
- Meeting proves a cycle.
- Restart one pointer at head; step together; they meet at the cycle start.
Complexity: O(n) time, O(1) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
Why not store visited nodes in a set?
How do you find the middle of a list?
Why is Find the Duplicate a cycle problem?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
When fast ends, slow is the middle.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Happy Number
Repeatedly replace n with the sum of squares of its digits. Does it reach 1?
- The sequence either reaches 1 or loops.
- Detect the loop with fast and slow pointers, without storing a set.
1function isHappy(n: number): boolean {2 const step = (x: number) =>3 [...String(x)].reduce((sum, d) => sum + Number(d) ** 2, 0);4 let slow = n, fast = step(n);5 while (fast !== 1 && slow !== fast) {6 slow = step(slow);7 fast = step(step(fast));8 }9 return fast === 1;10}Complexity: O(log n) per step, O(1) space
Find the Duplicate Number
n + 1 numbers in [1, n], one repeated. Find it in O(1) extra space without changing the array.
- Treat i → nums[i] as a linked list; the duplicate value is where two arrows enter one node.
- That makes a cycle; its entrance is the duplicate.
- Use Floyd's algorithm.
1function findDuplicate(nums: number[]): number {2 let slow = nums[0], fast = nums[0];3 do {4 slow = nums[slow];5 fast = nums[nums[fast]];6 } while (slow !== fast);7 slow = nums[0];8 while (slow !== fast) {9 slow = nums[slow];10 fast = nums[fast];11 }12 return slow;13}Complexity: O(n) time, O(1) space
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Checking fast.next.next without checking fast.next
- Comparing values instead of node identity