Coding Patterns - Fast and Slow Pointers

Intuition

The fast and slow pointer technique (also called Floyd’s Cycle Detection or the “tortoise and hare” method) is an extension of the two-pointer concept. Instead of moving both pointers at the same speed, one pointer moves one step at a time (slow), while the other moves two steps at a time (fast). This technique is widely used to detect cycles, find middle elements, and optimize traversal problems.

Think of it as two runners on a circular track: if they keep running, the faster runner will eventually catch up to the slower one if a cycle exists.

Fast and Slow Pointer Strategies

1. Cycle Detection in Linked Lists

• If fast and slow pointers meet, a cycle exists.

• If fast reaches the end, no cycle exists.

2. Finding the Middle of a Linked List

• When the fast pointer reaches the end, the slow pointer will be at the middle.

3. Detecting Palindromes in Linked Lists

• Use fast and slow pointers to reach the middle, then reverse the second half for comparison.

4. Finding Start of Cycle

• After detecting a cycle, reset one pointer to head and move both at the same pace; where they meet is the cycle’s start.

When To Use Fast and Slow Pointers

Use this technique when:

• Detecting cycles in a data structure.

• Locating midpoints efficiently.

• Working with problems that involve repetitive traversal like palindrome checking.

• You need O(n) time with O(1) extra space.

Real-World Example

Network Packet Routing: In certain distributed systems, circular paths (loops) can occur in routing. Fast and slow pointers can simulate message passing to detect if routing cycles exist.

Coding Example: Detect Cycle in Linked List

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

def has_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Example usage
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Creates cycle

print(has_cycle(node1))  # True

Framework

1. Initialize two pointers: slow (1 step) and fast (2 steps).

2. Traverse until fast reaches null (no cycle) or slow == fast (cycle found).

3. For middle element: stop when fast reaches end, return slow.

4. For cycle start: after detection, reset one pointer to head and move both step by step until they meet.

Key Points

• Fast and slow pointers reduce space usage vs. hash-based cycle detection.

• Applications: cycle detection, midpoint finding, palindrome validation.

• Elegant O(n) solutions with O(1) space.

Practice Exercise

Exercise: Write a function to find the middle node of a linked list using fast and slow pointers.

Sample Solution:

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

# Example usage
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

middle = find_middle(node1)
print(middle.val)  # 3