Does this linked list go on forever in a loop? Where is its middle? You can answer both with one beautiful idea from a children's story: the tortoise and the hare. In DSA it's called fast and slow pointers (or Floyd's cycle detection), and it's an interview favourite at Amazon and many product companies.
The 12 interview patterns: you are here
- 1Two Pointerssorted + pair
- 2Sliding Windowcontiguous subarray
- 3Prefix Sum + Hash Maprange sums, sum = K
- 4Binary Search on Answersmallest value that works
- 5Fast & Slow Pointerscycle, middle
- 6Merge Intervalsoverlapping ranges
- 7Monotonic Stackcoming soon
- 8Heap / Top-Kcoming soon
- 9Tree Patternscoming soon
- 10Grid BFS & Topological Sortcoming soon
- 11Backtrackingcoming soon
- 12DP Patternscoming soon
The race track story
Two friends run on a circular track, one twice as fast as the other. Sooner or later, the fast one laps the slow one and they're side by side. Now put them on a straight road with a finish line: the fast one just finishes first, and at that moment the slow one has covered exactly half the road.
A linked list with a loop is the circular track. Without a loop, it's the straight road. Race them:
π’π Race on a linked list: is there a loop?
β© node 7 points back to node 3
Turn 0: Both start at node 1. π’ moves 1 step, π moves 2 steps each turn.
With a loop, the hare can never escape, and it closes the gap by one node per turn, so they must meet. Without a loop, the hare simply falls off the end, and at that moment the tortoise is halfway.
Why they must meet (the 10-second proof)
Once both are inside the loop, every turn the hare moves 2 and the tortoise moves 1, so the gap between them shrinks by exactly 1. A gap of 4 becomes 3, 2, 1, 0. It can't skip zero, so they always land on the same node.
π Use fast & slow pointers when you see
- ββDoes this linked list have a cycle?β
- ββFind the middle nodeβ in one pass
- βA sequence that might repeat forever (happy number)
- βThe follow-up says βO(1) extra spaceβ
π« Don't use it when
- βArrays where you can just use indexes
- βPair-sum questions (two pointers from both ends)
- βYou're allowed O(n) memory and want the simplest code (a hash set works)
The template
slow = fast = head
while fast and fast.next: # hare can still hop 2
slow = slow.next # tortoise walks 1
fast = fast.next.next # hare hops 2
if slow is fast: return "cycle!"
return "no cycle" # and slow is now at the middleβ‘ Memory tricks
- 1
βTortoise walks 1, hare hops 2β
slow = slow.next, fast = fast.next.next.
- 2
βCircle β they meet. Road β hare finishes.β
Meeting means a cycle; reaching null means none.
- 3
βHare finishes, tortoise is halfwayβ
Twice the speed β half the distance: the middle node.
- 4
βCheck fast AND fast.nextβ
The hare hops two, so both must exist or you'll crash on null.
Code: middle node and cycle detection (Python, Java, C++)
Outputs in the comments come from running the code, including the version where node 5 points back to node 3.
class Node:
def __init__(self, val):
self.val = val
self.next = None
def build(values):
head = Node(values[0])
cur = head
for v in values[1:]:
cur.next = Node(v)
cur = cur.next
return head
def middle(head):
"""Hare moves 2, tortoise moves 1. When the hare finishes, the tortoise is halfway."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.val
def has_cycle(head):
"""On a looped track, the faster runner always catches the slower one."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
print(middle(build([1, 2, 3, 4, 5]))) # 3
print(middle(build([1, 2, 3, 4, 5, 6]))) # 4 (second middle)
track = build([1, 2, 3, 4, 5])
print(has_cycle(track)) # False
tail = track
while tail.next:
tail = tail.next
tail.next = track.next.next # 5 -> 3 makes a loop
print(has_cycle(track)) # TrueOne pattern, many problems
| Famous problem | How the pattern solves it | Level |
|---|---|---|
| Linked List Cycle | Slow 1, fast 2: meet = cycle | Easy |
| Middle of the Linked List | When fast ends, slow is the middle | Easy |
| Happy Number | Detect a loop in the digit-square sequence | Easy |
| Palindrome Linked List | Find middle, reverse second half, compare | Easy |
| Linked List Cycle II | Meet, then reset one to head, walk together | Medium |
| Reorder List | Find middle, reverse, weave together | Medium |
| Find the Duplicate Number | Treat values as next-pointers, find loop start | Medium |
π― Spot the pattern: is it fast & slow pointers?
In an interview nobody tells you the pattern. Read each problem and decide. Look for the signal words.
1. Check whether a linked list has a cycle, using O(1) extra memory.
2. Return the middle node of a linked list in one pass.
3. A number is βhappyβ if repeatedly summing the squares of its digits reaches 1. Check if n is happy.
4. Find two numbers in a sorted array that add up to 9.
5. Reverse a linked list.
π§ PATH memory card
Remember fast and slow pointers for good
Picture it Β· Anchor it Β· Trace it Β· Hit-recall it. Four quick steps that turn βI read it onceβ into βI can explain it in an examβ.
- P
Picture it
Your brain remembers scenes far better than definitions.
β swipe to see the whole picture β
On a circular track the faster runner always laps the slower one. On a straight road the fast one finishes first, and the slow one is halfway.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
βTortoise walks 1, hare hops 2: circle β they meet, road β tortoise is halfwayβ
- Tortoise walks 1βslow = slow.next
- Hare hops 2βfast = fast.next.next
- Circle β meetβslow == fast means there's a cycle
- Road β halfwayβfast hits null: no cycle, slow is at the middle
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
1β2β3β4β5β(back to 3). Turns: π’2 π3 Β· π’3 π5 Β· π’4 π4 β meet at 4: cycle! Without the loop: π’2 π3 Β· π’3 π5 β π can't hop β no cycle, middle = 3. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 7 Β· new0 mastered Β· 0 practisedSay the answer out loud first, then flip and be honest.
Common mistakes
- Checking only
fast. You also needfast.next, orfast.next.nextcrashes on null. - Comparing values instead of nodes. Two different nodes can hold the same value. Compare the node references.
- Checking for a meeting before moving. Both start at the head, so they're βequalβ at the start. Move first, then compare.
Where to go next
The last pattern in this batch is about time ranges: meetings, bookings, train schedules. Sort them and glue the overlaps together: merge intervals.
Key takeaways
- βSlow moves 1, fast moves 2.
- βThey meet β cycle. Fast reaches the end β no cycle.
- βWhen fast finishes, slow is at the middle.
- βO(n) time, O(1) space: the reason interviewers ask for it.
- βLoop condition: while fast and fast.next.
Frequently asked questions
What are fast and slow pointers?
Two pointers that move through a linked list (or sequence) at different speeds: the slow one moves 1 step, the fast one moves 2. If there's a loop, the fast one eventually catches the slow one. If there isn't, the fast one reaches the end, and at that moment the slow one is at the middle. It's also called Floyd's cycle detection or the tortoise and hare algorithm.
How do you detect a cycle in a linked list?
Start slow and fast at the head. Each turn, move slow by one node and fast by two. If they ever point to the same node, there's a cycle. If fast (or fast.next) becomes null, the list ends, so there's no cycle. Time O(n), space O(1).
Why do the fast and slow pointers always meet in a cycle?
Once both are inside the loop, the fast pointer gains exactly one node on the slow pointer every turn. The gap shrinks by one each time (β¦3, 2, 1, 0), so it can't jump over the slow pointer: they must land on the same node.
How do you find the middle of a linked list in one pass?
Move slow by 1 and fast by 2 until fast reaches the end. Since fast covers twice the distance, slow is exactly halfway. For an even number of nodes this gives the second middle (node 4 of 6); start fast at head.next for the first middle.
Why not just use a hash set to detect the cycle?
A hash set of visited nodes also works in O(n) time, but uses O(n) extra memory. Fast and slow pointers use O(1) memory, which is why interviewers ask for it as the follow-up.
π§ Quick check: fast and slow pointers
1. In cycle detection, how far does each pointer move per turn?
2. The fast pointer reaches null. What does that mean?
3. List 1β2β3β4β5, no loop. Where is slow when fast can't move further?
4. What's the extra space used by fast and slow pointers?
Checking your accessβ¦