boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
} func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast { return true }
}
return false
} def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False // Index-based approach (Rust ownership prevents pointer cycles)
fn has_cycle(next: &[Option<usize>]) -> bool {
let (mut slow, mut fast) = (0, 0);
loop {
slow = match next[slow] { Some(n) => n, None => return false };
fast = match next[fast] { Some(n) => n, None => return false };
fast = match next[fast] { Some(n) => n, None => return false };
if slow == fast { return true; }
}
} function hasCycle(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
} Detect cycles, find midpoints, and solve linked list problems using two pointers moving at different speeds.
The Fast & Slow Pointers technique (also known as Floyd's Tortoise and Hare) uses two pointers that traverse a sequence at different speeds. Typically, the slow pointer moves 1 step at a time, while the fast pointer moves 2 steps at a time.
After 2 iterations: slow is at node 3 (moved 2), fast is at node 5 (moved 4). The fast pointer advances twice as quickly, which creates the mathematical properties we exploit.
Core principle: If there is a cycle, the fast pointer will eventually "lap" the slow pointer and they will meet. If there is no cycle, the fast pointer hits the end first. This simple idea solves an entire family of problems in O(1) space.
Reach for the fast & slow pointers pattern whenever you see these signals:
The alternative is worse: Without this pattern, cycle detection requires a HashSet (O(n) space) to remember visited nodes. Fast & slow pointers achieve the same result in O(1) space.
Consider a linked list where the last node points back to an earlier node, creating a cycle. We deploy two pointers: slow moves 1 step, fast moves 2 steps.
Once both pointers are inside the cycle, think of the gap between them. Each iteration, fast gains exactly 1 step on slow (2 - 1 = 1). So the gap shrinks by 1 every step. No matter how large the cycle, the gap eventually reaches 0 -- they meet.
List: 1 → 2 → 3 → 4 → 5 → 6 → back to 3 (cycle)
// Cycle Detection ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps if (slow == fast) return true; // cycle found! } return false; // fast hit null, no cycle
// Cycle Detection slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next // 1 step fast = fast.Next.Next // 2 steps if slow == fast { return true // cycle found! } } return false // fast hit nil, no cycle
# Cycle Detection slow, fast = head, head while fast is not None and fast.next is not None: slow = slow.next # 1 step fast = fast.next.next # 2 steps if slow == fast: return True # cycle found! return False # fast hit None, no cycle
// Cycle Detection let mut slow = head.as_ref(); let mut fast = head.as_ref(); while let Some(f) = fast { if f.next.is_none() { break; } slow = slow.unwrap().next.as_ref(); // 1 step fast = f.next.as_ref().unwrap().next.as_ref(); // 2 steps if std::ptr::eq(slow.unwrap(), fast.unwrap()) { return true; // cycle found! } } return false; // fast hit None, no cycle
// Cycle Detection let slow = head, fast = head; while (fast !== null && fast.next !== null) { slow = slow!.next; // 1 step fast = fast.next.next; // 2 steps if (slow === fast) return true; // cycle found! } return false; // fast hit null, no cycle
After detecting the cycle (slow and fast meet), we can find where the cycle begins with a beautiful trick: reset one pointer to the head, then move both at speed 1. They will meet at the cycle start.
Let's define the distances:
This means: starting from the meeting point and walking F more steps lands exactly at the cycle start. And walking F steps from the head also lands at the cycle start. So they meet there!
// Find Cycle Start (Phase 1 + Phase 2) ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // Phase 2: reset slow to head, both move at speed 1 slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; // speed 1 now! } return slow; // cycle start } } return null; // no cycle
// Find Cycle Start (Phase 1 + Phase 2) slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next if slow == fast { // Phase 2: reset slow to head, both move at speed 1 slow = head for slow != fast { slow = slow.Next fast = fast.Next // speed 1 now! } return slow // cycle start } } return nil // no cycle
# Find Cycle Start (Phase 1 + Phase 2) slow, fast = head, head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow == fast: # Phase 2: reset slow to head, both move at speed 1 slow = head while slow != fast: slow = slow.next fast = fast.next # speed 1 now! return slow # cycle start return None # no cycle
// Find Cycle Start (Phase 1 + Phase 2) // Note: Rust's ownership model means cycle detection uses // raw pointer comparison for a true linked list with cycles. use std::collections::HashSet; let mut slow = head.as_ref(); let mut fast = head.as_ref(); let mut met = false; while let Some(f) = fast { if f.next.is_none() { break; } slow = slow.unwrap().next.as_ref(); fast = f.next.as_ref().unwrap().next.as_ref(); if std::ptr::eq(slow.unwrap(), fast.unwrap()) { met = true; break; } } if !met { return None; } // no cycle // Phase 2: reset slow to head, both move at speed 1 slow = head.as_ref(); while !std::ptr::eq(slow.unwrap(), fast.unwrap()) { slow = slow.unwrap().next.as_ref(); fast = fast.unwrap().next.as_ref(); // speed 1! } return Some(slow.unwrap()) // cycle start
// Find Cycle Start (Phase 1 + Phase 2) let slow = head, fast = head; while (fast !== null && fast.next !== null) { slow = slow!.next; fast = fast.next.next; if (slow === fast) { // Phase 2: reset slow to head, both move at speed 1 slow = head; while (slow !== fast) { slow = slow!.next; fast = fast!.next; // speed 1 now! } return slow; // cycle start } } return null; // no cycle
Since fast moves at 2x speed, when fast reaches the end of the list, slow is exactly at the middle. No need to count the length first!
List: 1 → 2 → 3 → 4 → 5 — watch both pointers advance.
Even-length lists: For a list with even number of nodes (e.g., 1→2→3→4), slow lands on the second middle node (node 3). If you need the first middle, check fast.next != null && fast.next.next != null instead.
// Find Middle of Linked List ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // middle node
// Find Middle of Linked List slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next // 1 step fast = fast.Next.Next // 2 steps } return slow // middle node
# Find Middle of Linked List slow, fast = head, head while fast is not None and fast.next is not None: slow = slow.next # 1 step fast = fast.next.next # 2 steps return slow # middle node
// Find Middle of Linked List let mut slow = head.as_ref(); let mut fast = head.as_ref(); while fast.is_some() && fast.unwrap().next.is_some() { slow = slow.unwrap().next.as_ref(); // 1 step fast = fast.unwrap().next.as_ref() .unwrap().next.as_ref(); // 2 steps } slow // middle node
// Find Middle of Linked List let slow = head, fast = head; while (fast !== null && fast.next !== null) { slow = slow!.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // middle node
Here are all three templates together, fully annotated. These are the building blocks for every fast & slow pointer problem.
public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // tortoise: 1 step fast = fast.next.next; // hare: 2 steps if (slow == fast) return true; // they met = cycle exists } return false; // fast reached end = no cycle }
func hasCycle(head *ListNode) bool { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next // tortoise: 1 step fast = fast.Next.Next // hare: 2 steps if slow == fast { return true // they met = cycle exists } } return false // fast reached end = no cycle }
def has_cycle(head: Optional[ListNode]) -> bool: slow, fast = head, head while fast is not None and fast.next is not None: slow = slow.next # tortoise: 1 step fast = fast.next.next # hare: 2 steps if slow == fast: return True # they met = cycle exists return False # fast reached end = no cycle
impl Solution { pub fn has_cycle(head: Option<Box<ListNode>>) -> bool { let mut slow = head.as_ref(); let mut fast = head.as_ref(); while fast.is_some() && fast.unwrap().next.is_some() { slow = slow.unwrap().next.as_ref(); // tortoise: 1 step fast = fast.unwrap().next.as_ref() .unwrap().next.as_ref(); // hare: 2 steps if std::ptr::eq(slow.unwrap(), fast.unwrap()) { return true; // they met = cycle exists } } false // fast reached end = no cycle } }
function hasCycle(head: ListNode | null): boolean { let slow = head, fast = head; while (fast !== null && fast.next !== null) { slow = slow!.next; // tortoise: 1 step fast = fast.next.next; // hare: 2 steps if (slow === fast) return true; // they met = cycle exists } return false; // fast reached end = no cycle }
public ListNode detectCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // Phase 1: detect cycle slow = head; // Phase 2: reset to head while (slow != fast) { slow = slow.next; // both move at speed 1 fast = fast.next; } return slow; // meeting point = cycle start } } return null; // no cycle }
func detectCycle(head *ListNode) *ListNode { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next if slow == fast { // Phase 1: detect cycle slow = head // Phase 2: reset to head for slow != fast { slow = slow.Next // both move at speed 1 fast = fast.Next } return slow // meeting point = cycle start } } return nil // no cycle }
def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]: slow, fast = head, head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow == fast: # Phase 1: detect cycle slow = head # Phase 2: reset to head while slow != fast: slow = slow.next # both move at speed 1 fast = fast.next return slow # meeting point = cycle start return None # no cycle
impl Solution { pub fn detect_cycle(head: Option<Box<ListNode>>) -> Option<&ListNode> { let mut slow = head.as_ref(); let mut fast = head.as_ref(); let mut met = false; while fast.is_some() && fast.unwrap().next.is_some() { slow = slow.unwrap().next.as_ref(); fast = fast.unwrap().next.as_ref() .unwrap().next.as_ref(); if std::ptr::eq(slow.unwrap(), fast.unwrap()) { met = true; break; // Phase 1: detected } } if !met { return None; } // no cycle // Phase 2: reset slow to head, both at speed 1 slow = head.as_ref(); while !std::ptr::eq(slow.unwrap(), fast.unwrap()) { slow = slow.unwrap().next.as_ref(); fast = fast.unwrap().next.as_ref(); } Some(slow.unwrap()) // cycle start } }
function detectCycle(head: ListNode | null): ListNode | null { let slow = head, fast = head; while (fast !== null && fast.next !== null) { slow = slow!.next; fast = fast.next.next; if (slow === fast) { // Phase 1: detect cycle slow = head; // Phase 2: reset to head while (slow !== fast) { slow = slow!.next; // both move at speed 1 fast = fast!.next; } return slow; // meeting point = cycle start } } return null; // no cycle }
public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // when fast stops, slow = middle }
func middleNode(head *ListNode) *ListNode { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next // 1 step fast = fast.Next.Next // 2 steps } return slow // when fast stops, slow = middle }
def middle_node(head: Optional[ListNode]) -> Optional[ListNode]: slow, fast = head, head while fast is not None and fast.next is not None: slow = slow.next # 1 step fast = fast.next.next # 2 steps return slow # when fast stops, slow = middle
impl Solution { pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut slow = head.as_ref(); let mut fast = head.as_ref(); while fast.is_some() && fast.unwrap().next.is_some() { slow = slow.unwrap().next.as_ref(); // 1 step fast = fast.unwrap().next.as_ref() .unwrap().next.as_ref(); // 2 steps } // clone the middle node out (LeetCode uses Box-based list) slow.cloned() // middle node } }
function middleNode(head: ListNode | null): ListNode | null { let slow = head, fast = head; while (fast !== null && fast.next !== null) { slow = slow!.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // when fast stops, slow = middle }
Notice the pattern: All three share the exact same loop structure. The only differences are (1) what happens when slow == fast, and (2) what we return. Master the loop skeleton once, then adapt the response.
These LeetCode problems are solved cleanly using the fast & slow pointers pattern.
#287 Find the Duplicate Number is a particularly clever application: treat the array indices as linked list nodes where nums[i] is the "next" pointer. A duplicate value means two nodes point to the same next -- creating a cycle. Apply Floyd's algorithm to find the duplicate without extra space!
Watch the pointers move step by step through real linked lists.
Cycle detection: If there is no cycle, fast pointer traverses the list once = O(n). If there is a cycle, once both pointers enter the cycle, they meet within at most C steps (where C = cycle length). Since C ≤ n, total work is O(n).
Finding cycle start: Phase 1 is O(n). Phase 2 walks at most F steps (distance from head to cycle start), which is ≤ n. Total: O(n).
Finding middle: Fast pointer traverses the entire list once = O(n). Slow pointer does n/2 steps.
O(1) space is the real win. A HashSet-based cycle detection uses O(n) space to store visited nodes. Floyd's algorithm uses only two pointer variables, no matter how large the input. This is the hallmark of the pattern.
Problems that seem to require O(n) space (storing visited nodes, counting length) can often be solved in O(1) space with fast & slow pointers.
All three use cases share the same while loop. Master it once: while (fast != null && fast.next != null).
Any function f(x) that maps values to values can form a "virtual linked list." Happy Number and Find Duplicate both exploit this.
Finding the cycle start uses two phases: (1) detect with 2x speed, (2) reset one pointer and walk both at 1x. The math guarantees they meet at the start.
The Beauty of Floyd's Algorithm
Two pointers, constant space, linear time. It turns problems that seem to need memory into problems that need only patience -- letting two runners chase each other until the structure of the problem reveals itself.