BeginnerLinked Lists

Fast–Slow Pointers

Use two pointers at different speeds to detect cycles and locate positions

Time: O(n)
Space: O(1)
Pattern Overview

Core Idea

Advance fast by 2 and slow by 1 to detect cycles; use gaps to find middle or Nth-from-end.

When to Use

Use on linked lists for cycle detection/entry, middle node, or removing Nth from end in one pass.

General Recognition Cues
General indicators that this pattern might be applicable
  • Cycle detection
  • Find middle
  • Nth from end
  • One pass
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Cycle Detection

Floyd's tortoise and hare to detect cycle

When to Use This Variant
  • Meet if cycle
  • fast=fast.next.next
Use Case
Detect and locate cycle
Advantages
  • O(1) space
  • Linear time
Implementation
def detect_cycle(head):
    # Returns entry node if cycle exists, else None
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None
2

Middle Node

Move fast twice as fast to find middle

When to Use This Variant
  • Middle of list
Use Case
Split list
Advantages
  • One pass
  • Constant space
Implementation
def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
3

Remove Nth From End

Maintain gap N between pointers

When to Use This Variant
  • Nth from end
Use Case
Deletion in one pass
Advantages
  • One pass
  • Simple
Implementation
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n):
        fast = fast.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next
Common Pitfalls
Watch out for these common mistakes
  • Null checks on fast/fast.next
  • Reset logic after meeting
  • Edge cases with size < N
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Traverse each node O(1) times.

Space Complexity
O(1)

Only pointers used.

Ready to test your knowledge?

Test your pattern recognition with interactive questions