Two walkers on the same track at different speeds. If the track loops, the fast one laps the slow one, and that collision is a cycle detector using no memory at all.
Also called Floyd’s tortoise and hare. It answers a question that looks like it needs a hash set, have I been here before, using two pointers and nothing else. The interviewer is usually testing whether you can get from the O(n)-space answer to the O(1)-space answer.
next. An index i maps to nums[i]. A number maps to the sum of the squares of its digits. Any such function traces a path that must eventually repeat, and the question is about that repetition or about a position along the path.| Signal | What it looks like |
|---|---|
| Cycle language | “does the list have a cycle”, “where does the loop start”, “does it repeat forever”. |
| Positional language | “the middle node”, “the k-th from the end”, “the second half”. One pass, no length count. |
| Space constraint | “O(1) extra space” on a problem where a visited set is the obvious answer. |
| Read-only array | “you must not modify the array” turns an array problem into an implicit linked list. |
i → nums[i] is a next pointer and the array is a linked structure. Once you see that, “find the duplicate” becomes “find the start of the cycle”. Recognising this disguise is the single highest-value thing on this page.slow one step and fast two steps per iteration. If the path is finite and has no cycle, fast falls off the end and you are done. If there is a cycle, both pointers end up inside it, and since fast gains exactly one position on slow every iteration, the gap shrinks by one each time and must hit zero. They cannot jump past each other.Once both pointers are inside the cycle, let d be the number of positions fast is behind slow, measured going forward around the cycle. Each iteration fast advances 2 and slow advances 1, so d decreases by exactly 1, modulo the cycle length. It therefore reaches 0 within λ iterations. Because the change is exactly one per step, they cannot step over each other, which is why the speeds must be 1 and 2 and not, say, 1 and 3.
slow has taken μ + k steps for some k, and fast has taken 2(μ + k). Their difference, μ + k, must be a whole number of laps, so μ + k ≡ 0 (mod λ).
μ + k + μ steps in total, and since μ + k is a multiple of λ, that lands it exactly μ steps into the cycle too. They meet at the cycle start.This second phase is what turns cycle detection into cycle location, and it is the whole trick behind Find the Duplicate Number.
from dataclasses import dataclass
@dataclass
class ListNode:
"""A singly linked list node."""
val: int = 0 # 0: a neutral default value
next: "ListNode | None" = None # None: no next node, the list ends here
def detect(head: ListNode | None) -> ListNode | None:
"""Return the meeting node if a cycle exists, else None."""
slow = fast = head # both start at the head
# Invariant: fast has taken twice as many steps as slow.
# Checking fast and fast.next first keeps the two-step move safe.
while fast is not None and fast.next is not None:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
# In a cycle, fast gains 1 node per pass, so it must land on slow.
if slow is fast:
return slow
return None # fast ran off the end: no cycle
The guard fast is not None and fast.next is not None covers both odd and even list lengths. Test fast before dereferencing fast.next.
def cycle_start(head: ListNode | None) -> ListNode | None:
"""Return the first node of the cycle, or None if there is none."""
meeting = detect(head)
if meeting is None:
return None # no cycle, so no start node
# The head and the meeting point sit the same distance from the cycle start.
# So two pointers that move at the same speed meet exactly there.
walker = head
# Invariant: walker and meeting are the same distance from the cycle start.
while walker is not meeting: # both move one step at a time
walker = walker.next
meeting = meeting.next
return walker
Reading the figure. Amber nodes are where the two pointers start phase 2. Green S is the cycle start, where they meet. Count the arrows: three from h to S, and three from M forward to S.
fast.next.next without checking fast.next. On an even-length list this is an AttributeError. The two-part guard is not optional.== instead of is. For nodes you want identity. Two different nodes holding the same value are not the same node, and a __eq__ from a dataclass will happily say they are.slow is fast before moving. They start equal, so the check must come after the moves, or you report a cycle immediately.while fast and fast.next gives the second middle. Read the problem statement for which one it wants.Given the head of a linked list, return True if the list has a cycle in it. Solve it with O(1) extra memory.
fast ever reaches None, the list ends and there is no cycle. If there is a cycle, fast never escapes it, and it closes the gap on slow by one per step.def has_cycle(head: ListNode | None) -> bool:
"""Return True if the linked list contains a cycle.
Args:
head: First node, or None for an empty list.
Returns:
True if following .next repeats a node forever.
"""
slow = fast = head # both start at the head
# Invariant: fast has taken twice as many steps as slow.
# Checking fast and fast.next first keeps the two-step move safe.
while fast is not None and fast.next is not None:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps: gains 1 node on slow per pass
if slow is fast: # identity, not equality
return True
return False # fast hit the end, so the list has no loop
List 3 → 2 → 0 → -4 with -4 pointing back to 2:
| iteration | slow at | fast at |
|---|---|---|
| start | 3 | 3 |
| 1 | 2 | 0 |
| 2 | 0 | 2 |
| 3 | -4 | -4 |
Reading the figure. Each panel is one turn. Amber nodes hold slow or fast. The curved arrow is the link from −4 back to 2 that makes the cycle. Green is the meeting node.
They meet at -4, so the answer is True.
Time bound: slow takes at most μ steps to enter the cycle, then at most λ more before fast catches it, so at most μ + λ ≤ n iterations.
False.next = None: same.fast.next is the node, so one iteration puts both on it, returns True.Return the middle node of a singly linked list. If there are two middles, return the second one.
n // 2 nodes. Correct but two traversals.fast has covered the whole list at double speed, slow has covered exactly half of it. No length needed, and it works on a stream you can only read once.def middle_node(head: ListNode | None) -> ListNode | None:
"""Return the middle node; the second middle if the length is even.
Args:
head: First node, or None.
Returns:
The middle node, or None for an empty list.
"""
slow = fast = head # both start at the head
# Invariant: fast has taken twice as many steps as slow.
# So when fast reaches the end, slow is halfway.
while fast is not None and fast.next is not None:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
# Even length: fast ends at None, which leaves slow on the second middle.
return slow
| Loop guard | Even-length result | Use it when |
|---|---|---|
| while fast and fast.next | second middle | The problem says “return the second middle”. |
| while fast.next and fast.next.next | first middle | You need the node before the split, for example to cut the list in two for merge sort. |
The second variant needs a non-empty list, so guard head first. For a list of length 4 the first gives node 3 and the second gives node 2.
List 1 → 2 → 3 → 4 → 5. After two iterations slow is at 3 and fast is at 5, whose next is None, so the loop stops. Answer 3. For 1 → 2 → 3 → 4, slow ends at 3, the second middle.
Reading the figure. Amber cells hold slow or fast. Green is the node returned. In the last row fast has run off the end, so it has no cell.
Start with a positive integer. Replace it by the sum of the squares of its digits, and repeat. The number is happy if this eventually reaches 1. Otherwise it loops forever without reaching 1. Return whether n is happy.
value → sum of squared digits. That is all the pattern needs.3 × 9² = 243, so the sequence is eventually trapped below 243 and cannot run away. A finite state space with a deterministic successor always ends in a cycle.1 is a fixed point, 1 → 1. So “happy” is exactly “the cycle you land in is the one containing 1”. Run the tortoise and hare and check where they end up.def is_happy(n: int) -> bool:
"""Return True if repeatedly summing squared digits reaches 1.
Args:
n: A positive integer.
Returns:
True if n is a happy number.
Example:
>>> is_happy(19)
True
"""
def next_value(value: int) -> int:
"""Sum of the squares of the decimal digits of value."""
total = 0 # 0: empty sum
# Invariant: total holds the squares of the digits already peeled off.
while value > 0: # 0: no digits left
# 10: base ten. divmod peels off the last digit.
value, digit = divmod(value, 10)
total += digit * digit # digit squared
return total
# The sequence n, next(n), ... is a linked list of numbers.
# It either hits 1 and stays there, or loops. Floyd tells the two apart.
slow, fast = n, next_value(n) # fast starts 1 step ahead so the loop can run
# Stop on success (fast reaches the 1 fixed point) or on a collision.
# 1: next_value(1) == 1, so 1 is a loop of length one.
while fast != 1 and slow != fast:
slow = next_value(slow) # 1 step
fast = next_value(next_value(fast)) # 2 steps
return fast == 1 # 1: we stopped because we reached 1
n = 19. The sequence is 19, 82, 68, 100, 1.
| slow | fast | note |
|---|---|---|
| 19 | 82 | initial |
| 82 | 100 | fast took two steps |
| 68 | 1 | loop exits, happy |
Reading the figure. Each arrow is one call to next_value. Amber cells hold slow or fast. Green 1 means happy. The red ring is the cycle that 2 falls into, where the pointers would meet without ever seeing 1.
For n = 2 the sequence enters the cycle 4, 16, 37, 58, 89, 145, 42, 20, 4, the pointers collide inside it, and the answer is False.
The first next_value call is O(log n) in the number of digits and collapses n to at most 243 immediately, after which the work is bounded by a constant.
n = 1: fast starts at next_value(1) == 1, the loop never runs, returns True.n = 7: happy, via a longer path. Good sanity check.An array nums of n + 1 integers holds values in the range 1..n. Exactly one value is repeated, possibly many times. Find it, without modifying the array and using O(1) extra space.
| Approach | Blocked by |
|---|---|
| Sort, then scan neighbours | “do not modify the array” |
| Hash set of seen values | “O(1) extra space” |
| Cyclic sort, swapping values home | “do not modify the array” |
| Sum formula | The value may repeat more than twice |
| Floyd on the index graph | Nothing. This is the intended answer. |
m, count how many values are ≤ m; if that count exceeds m, the duplicate is at or below m. That is O(n log n) time and O(1) space, and it is easier to derive under pressure. Have it as your backup.i → nums[i]. Values are in 1..n and indices in 0..n, so every value is a valid index and the walk never leaves the array.0. Index 0 is never a value, since values start at 1, so nothing points back into the start and the path has a genuine tail. That guarantees the rho shape rather than a pure loop.def find_duplicate(nums: list[int]) -> int:
"""Find the one repeated value in nums, read-only and in O(1) space.
Treats nums as a functional graph i -> nums[i]. The repeated value is
the entrance of the cycle that walk falls into.
Args:
nums: n + 1 integers, each in 1..n, with exactly one value repeated.
Returns:
The repeated value.
Example:
>>> find_duplicate([1, 3, 4, 2, 2])
2
"""
# Phase 1: find a meeting point inside the cycle.
# nums[0]: index 0 is the start. No value is 0, so nothing points back to it.
slow = fast = nums[0]
# Invariant: fast has taken twice as many steps as slow.
while True: # a cycle always exists, so this ends
slow = nums[slow] # 1 step
fast = nums[nums[fast]] # 2 steps
if slow == fast:
break
# Phase 2: walk one pointer from the start. They meet at the entrance.
# (Same trick as cycle_start: equal distances to the entrance.)
finder = nums[0] # nums[0]: one step from the start, like slow
# Invariant: finder and slow are the same distance from the entrance.
while finder != slow:
finder = nums[finder] # 1 step
slow = nums[slow] # 1 step
return finder
nums = [1, 3, 4, 2, 2]. The walk from index 0 is 0 → 1 → 3 → 2 → 4 → 2 → 4 → …, a tail of 0, 1, 3 feeding the cycle 2, 4. Two arrows point at node 2, from index 3 and from index 4, and those are the two positions holding the value 2.
| Phase | slow | fast / finder |
|---|---|---|
| 1 start | 1 | 1 |
| 1 step 1 | 3 | 2 |
| 1 step 2 | 2 | 2 |
| 2 start | 2 | 1 |
| 2 step 1 | 4 | 3 |
| 2 step 2 | 2 | 2 |
Reading the figure. Green cells hold the repeated value, and green node 2 is the answer. Two arrows enter it: from index 3 and from index 4. Violet node 4 is the rest of the cycle. The text on the right lists where each pointer sits after each step.
They meet at 2, the answer.
[2, 2, 2, 2, 2]: still one cycle entrance, still correct. This is exactly what breaks the sum-formula trick.[1, 1]: n = 1, the walk is 0 → 1 → 1, answer 1.0 is a safe start: no value equals 0, so node 0 has in-degree zero and can never be inside the cycle.do-while shape matters. Phase 1 must move before comparing, which is why it is while True with a break rather than a normal while slow != fast. The pointers start equal; a top-tested loop would exit immediately.nums is a next pointer and the array is a linked list. Two indices holding the same value are two arrows into one node, which is a cycle entrance, so the duplicate is exactly the cycle start.”μ + k ≡ 0 (mod λ). Be able to write that line.while fast is not None and fast.next is not None, and compare nodes with is.Pattern 4, Merge Intervals, leaves pointers behind. It is the first pattern where the whole insight is what to sort by, and where a greedy sweep replaces a search.