CodeMosa

Master LeetCode Patterns

BeginnerLinked ListsRead Linked Lists Fundamentals →

Fast–Slow Pointers

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

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

What is Fast–Slow Pointers?

#
Definition: Run two pointers at different speeds to detect cycles and locate positions like middle or Nth-from-end.

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.

How Fast–Slow Pointers works

#

Floyd's tortoise-hare for cycle detection/entry and pointer gap tricks for middle and N-th-from-end nodes.

  • Cycle detection
  • Find middle
  • Nth from end

General Recognition Cues

#
General indicators that this pattern might be applicable
  • Cycle detection
  • Find middle
  • Nth from end
  • One pass

Code Templates

#
Floyd's tortoise-hare for cycle detection/entry and pointer gap tricks for middle and N-th-from-end nodes.
# Fast/Slow Pointers Templates
def detect_cycle(head):
    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

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

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

Related Patterns

#
In-place ReversalMerge/Split Lists

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