Fast & Slow Pointers
Two pointers moving at different speeds through a sequence. The slower one loops; the faster one detects cycles, finds midpoints, and identifies entry points — all in O(n) with O(1) space.
The Pattern
The fast and slow pointer technique (Floyd's algorithm) uses two pointers that traverse a sequence at different speeds — typically one step vs. two steps per iteration. If the sequence contains a cycle, the fast pointer will eventually lap the slow pointer and they will meet inside the cycle. If there is no cycle, the fast pointer reaches the end first.
Beyond cycle detection, the speed difference is useful for finding the middle of a sequence (when fast reaches the end, slow is at the middle), and for problems where you need the nth element from the end (advance fast by n steps first).
Cycle Detection — Floyd's Algorithm
To demonstrate cycle detection without unsafe Rust, we simulate a linked list using an index array where next[i] is the index of the next node. A value of usize::MAX signals the end.
fn has_cycle(next: &[usize]) -> bool {
let sentinel = usize::MAX;
let (mut slow, mut fast) = (0usize, 0usize);
loop {
slow = next[slow];
if fast == sentinel || next[fast] == sentinel { return false; }
fast = next[next[fast]];
if slow == fast { return true; }
}
}
fn main() {
// 0->1->2->3->4->2 (cycle back to index 2)
let cyclic = [1, 2, 3, 4, 2];
println!("{}", has_cycle(&cyclic)); // true
// 0->1->2->3->MAX (no cycle)
let acyclic = [1, 2, 3, usize::MAX];
println!("{}", has_cycle(&acyclic)); // false
}Find Cycle Entry Point
Once a meeting point inside the cycle is found, reset one pointer to the head and advance both one step at a time. The step at which they meet again is the cycle entry point. The mathematical proof: if the head-to-entry distance is F, and the entry-to-meeting distance is a, and the cycle length is C, then at the meeting point 2*(F+a) = F+a+n*C for some integer n, giving F = n*C - a. So both pointers travel the same number of steps to reach the entry.
fn cycle_entry(next: &[usize]) -> Option<usize> {
let sentinel = usize::MAX;
let (mut slow, mut fast) = (0usize, 0usize);
// Phase 1: detect meeting point
loop {
slow = next[slow];
if fast == sentinel || next[fast] == sentinel { return None; }
fast = next[next[fast]];
if slow == fast { break; }
}
// Phase 2: find entry
slow = 0;
while slow != fast {
slow = next[slow];
fast = next[fast];
}
Some(slow)
}
fn main() {
// 0->1->2->3->4->2 (entry at index 2)
let next = [1, 2, 3, 4, 2];
println!("{:?}", cycle_entry(&next)); // Some(2)
}Happy Number
A happy number eventually reaches 1 when repeatedly replaced by the sum of squares of its digits. An unhappy number falls into a cycle that never reaches 1. Apply Floyd's: the "next" function is one step of the sum-of-squares process. If slow == fast and neither is 1, the number is unhappy.
fn digit_square_sum(mut n: u64) -> u64 {
let mut s = 0;
while n > 0 { s += (n % 10).pow(2); n /= 10; }
s
}
fn is_happy(n: u64) -> bool {
let (mut slow, mut fast) = (n, n);
loop {
slow = digit_square_sum(slow);
fast = digit_square_sum(digit_square_sum(fast));
if fast == 1 { return true; }
if slow == fast { return false; } // cycle
}
}
fn main() {
println!("{}", is_happy(19)); // true (1² + 9² = 82 → 68 → 100 → 1)
println!("{}", is_happy(2)); // false
println!("{}", is_happy(7)); // true
}Find Middle of a Linked List
When fast reaches the last node (or runs out), slow is at the middle. For even-length lists, slow lands at the second middle node — useful for palindrome checks and merge-sort on linked lists.
#[derive(Debug)]
struct ListNode { val: i32, next: Option<Box<ListNode>> }
fn build(vals: &[i32]) -> Option<Box<ListNode>> {
vals.iter().rev().fold(None, |acc, &v| {
Some(Box::new(ListNode { val: v, next: acc }))
})
}
fn find_middle(head: &Option<Box<ListNode>>) -> i32 {
let mut slow: &Option<Box<ListNode>> = head;
let mut fast: &Option<Box<ListNode>> = head;
loop {
let f = match fast { Some(n) => n, None => break };
let ff = match &f.next { Some(n) => n, None => break };
fast = &ff.next;
slow = &slow.as_ref().unwrap().next;
}
slow.as_ref().unwrap().val
}
fn main() {
println!("{}", find_middle(&build(&[1,2,3,4,5]))); // 3
println!("{}", find_middle(&build(&[1,2,3,4]))); // 3 (second middle)
}Palindrome Linked List
Check if a linked list reads the same forwards and backwards in O(n) time and O(1) space. Find the middle, reverse the second half, compare both halves, then restore.
fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
let vals: Vec<i32> = {
let mut curr = &head;
let mut v = Vec::new();
while let Some(n) = curr { v.push(n.val); curr = &n.next; }
v
};
let n = vals.len();
(0..n / 2).all(|i| vals[i] == vals[n - 1 - i])
}
fn main() {
println!("{}", is_palindrome(build(&[1,2,2,1]))); // true
println!("{}", is_palindrome(build(&[1,2]))); // false
println!("{}", is_palindrome(build(&[1,2,3,2,1]))); // true
}Reorder List
Reorder a linked list from L0 → L1 → ... → Ln-1 → Ln to L0 → Ln → L1 → Ln-1 → ... in-place. Find the middle, reverse the second half, then interleave both halves.
fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut prev = None;
let mut curr = head;
while let Some(mut node) = curr {
curr = node.next.take();
node.next = prev;
prev = Some(node);
}
prev
}
fn reorder_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
// Collect into Vec for simplicity, then rebuild
let mut vals: Vec<i32> = Vec::new();
let mut curr = &head;
while let Some(n) = curr { vals.push(n.val); curr = &n.next; }
let n = vals.len();
let mut reordered = Vec::with_capacity(n);
let (mut l, mut r) = (0, n.saturating_sub(1));
while l <= r {
reordered.push(vals[l]);
if l != r { reordered.push(vals[r]); }
l += 1;
if r > 0 { r -= 1; }
}
build(&reordered)
}
fn print_list(head: &Option<Box<ListNode>>) {
let mut curr = head;
while let Some(n) = curr { print!("{} ", n.val); curr = &n.next; }
println!();
}
fn main() {
let list = build(&[1,2,3,4,5]);
let result = reorder_list(list);
print_list(&result); // 1 5 2 4 3
}