5 questions using this pattern
Use two pointers moving at different speeds to detect cycles, find midpoints, or identify patterns in sequences. The fast pointer advances twice as quickly, allowing detection of structural properties without extra space.
Imagine two runners on a circular track. If one runs twice as fast as the other, the fast runner will eventually lap the slow runner—they'll meet at some point on the track. This proves the track is circular (has a cycle).
Another analogy: finding the middle of a line of people. Have two people start at the front—one takes one step at a time, the other takes two. When the fast person reaches the end, the slow person is at the middle.
The fast & slow pointers technique (also called Floyd's cycle detection or "tortoise and hare") uses two pointers moving at different speeds:
Key insights:
Cycle detection: In a cyclic structure, fast will eventually catch up to slow (they'll meet inside the cycle). In a non-cyclic structure, fast will reach the end.
Finding middle: When fast reaches the end, slow is at the middle (fast traveled 2x the distance).
Finding cycle start: After detecting a cycle, reset one pointer to start. Move both at the same speed—they meet at the cycle start. (Mathematical proof: the distances work out perfectly.)
def find_middle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slowWe have a linked list: 1 → 2 → 3 → 4 → 5 → null. Find the middle node.
Cycle Detection:
List: 1 → 2 → 3 → 4 → 5
↑ ↓
7 ← 6
Step 1: slow=1, fast=1
Step 2: slow=2, fast=3
Step 3: slow=3, fast=5
Step 4: slow=4, fast=7
Step 5: slow=5, fast=4
Step 6: slow=6, fast=6 ← They meet! Cycle exists.
Finding Middle:
List: 1 → 2 → 3 → 4 → 5 → null
Step 1: slow=1, fast=1
Step 2: slow=2, fast=3
Step 3: slow=3, fast=5
Step 4: fast reaches null
slow is at middle (3)
Finding Cycle Start:
After detecting cycle at node X:
1. Reset slow to head, keep fast at meeting point
2. Move both at same speed (1 step each)
3. They meet at cycle start
Why? Math: Let's say:
- Distance from head to cycle start = A
- Distance from cycle start to meeting point = B
- Cycle length = C
At meeting: slow traveled A + B
fast traveled A + B + nC (some complete cycles)
Since fast travels 2x: 2(A + B) = A + B + nC
Therefore: A + B = nC, so A = nC - B = (n-1)C + (C-B)
This means: distance from head to cycle start
= distance from meeting point to cycle start (going forward)
Use this skeleton as a starting point for problems using this pattern:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode) -> bool:
"""Detect if linked list has a cycle."""
if not head or not head.next:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def find_cycle_start(head: ListNode) -> ListNode:
"""Find the node where the cycle begins."""
if not head or not head.next:
return None
# Phase 1: Detect cycle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle
# Phase 2: Find cycle start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
def find_middle(head: ListNode) -> ListNode:
"""Find the middle node of linked list."""
if not head:
return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # Middle (or second middle if even length)
def is_happy_number(n: int) -> bool:
"""Check if number is happy (sum of squared digits eventually = 1)."""
def get_next(num: int) -> int:
total = 0
while num > 0:
digit = num % 10
total += digit * digit
num //= 10
return total
slow = n
fast = get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1
def is_palindrome_linked_list(head: ListNode) -> bool:
"""Check if linked list is a palindrome."""
if not head or not head.next:
return True
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
# Compare halves
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return TrueLook for these keywords and patterns in problem descriptions:
Accessing fast.next.next without first checking fast.next causes
null pointer errors when the list has even length.
Fix:
Always check both fast and fast.next:
while fast and fast.next:
fast = fast.next.next
Starting slow and fast at different positions (e.g., slow=head, fast=head.next) changes the math for finding the cycle start.
Fix:
Start both at head for consistency. The algorithms are designed assuming both start at the same position.
Determine if a linked list or sequence has a cycle. If fast catches slow, there's a cycle.
Examples: Linked List Cycle, Circular Array Loop
After detecting a cycle, find the node where the cycle begins using the two-phase approach.
Examples: Linked List Cycle II
When fast reaches the end, slow is at the middle. Useful for divide and conquer on linked lists.
Examples: Middle of Linked List, Sort List (merge sort needs middle)
Treat the sequence of digit-square sums as a linked list. Either reaches 1 (happy) or cycles (unhappy).
Examples: Happy Number
Find middle, reverse second half, compare. Combines finding middle with linked list reversal.
Examples: Palindrome Linked List
Start here to build foundational understanding.
Master the pattern with these representative problems.
Explore similar techniques:
Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.
Reverse linked list nodes in-place by manipulating pointers without allocating extra space. This technique uses three pointers to track the previous, current, and next nodes while systematically reversing the direction of links.
Accessing head.next or head.next.next on empty or single-node lists causes errors.
Fix:
Add early returns:
if not head or not head.next:
return False # or appropriate value
Returning the meeting point instead of finding the actual cycle start gives the wrong answer.
Fix:
After detecting a cycle (meeting point), reset one pointer to head and advance both at the same speed to find the cycle start.