Fast & Slow pointers is a technique that uses two pointers moving at different speeds through a linked list. The slow pointer moves one step at a time while the fast pointer moves multiple steps. This difference in speed helps detect cycles and find middle elements in linked lists, similar to how a faster runner would eventually catch up to a slower one on a circular track.

Fast & slow pointers, also known as Tortoise and Hare, is a technique that uses two pointers moving at different speeds through a linked list. The slow pointer (tortoise) moves one step at a time, while the fast (hare) moves two steps. This difference in speed allows us to find the middle of the list, as the fast pointer will reach the end when the slow pointer is at the middle.

# Definition for singly-linked list node
class ListNode:
    def __init__(self, val: int = 0, next: Optional[ListNode] = None):
        self.val = val
        self.next = next    

class FastAndSlowPointers:
    def findMiddleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: If the head doesn't exist, return None
        if not head:
            return None
        
        # Initialize fast & slow pointers at the head of the list   
        slow = head
        fast = head
        
        # Move fast pointer two steps and slow pointer one step until fast reaches the end
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Return the slow pointer, which is now at the middle of the list
        return slow

What makes this algorithm powerful is its space efficiency. Unlike storing nodes in an array or counting the length first, the tortoise and hare approach finds the middle element in a single pass without using extra space. This makes it ideal for memory-constrained environments and problems that require finding the middle element of a linked list.

Cycle detection is the primary application of Fast & Slow pointers, used to find loops in a linked list. When a fast pointer moving two steps meets a slow pointer moving one step, their intersection confirms the presence of a cycle.This works because in a cycle, the fast pointer will eventually catch up to the slow pointer, similar to a faster runner overlapping a slower one on a circular track.

# Definition for singly-linked list node
class ListNode:
    def __init__(self, val: int = 0, next: Optional[ListNode] = None):
        self.val = val
        self.next = next    

class FastAndSlowPointers:
    def findCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: If the head doesn't exist, return None
        if not head:
            return None
        
        # Initialize fast & slow pointers at the head of the list
        slow = head
        fast = head

        # Move fast pointer two steps and slow pointer one step
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            # If slow and fast pointers meet, there is a cycle  
            if slow == fast:
                # Find the start of the cycle
                cur = head
                while cur != slow:
                    cur = cur.next
                    slow = slow.next
                return cur
        
        # If no cycle exists, return None
        return None

After detecting a cycle, we can find its starting point by moving one pointer to the head of the list and advancing both pointers one step at a time. The point where they meet again marks the beginning of the cycle. This technique efficiently solves cycle-related problems using O(1) extra space, making it ideal for memory-constrained scenarios.

Fast & Slow pointers work by exploiting speed ratios between two pointers. The slow pointer moves one step while the fast pointer can move any number of steps through a linked list. By adjusting this ratio, we can find different positions - using two steps finds the middle, three steps finds the first third, and so on. This flexible approach allows us to divide a linked list into any proportion we need, all while maintaining the same simple implementation.

The initial placement of these pointers can affect where slow lands in the list. Starting fast at head.next instead of head causes slow to stop one position earlier - landing at the left-middle node in even-length lists and one node before the middle in odd-length lists. This variation is particularly useful when implementing algorithms that need the left-middle position, such as converting a sorted linked list to a balanced binary search tree.

The beauty of this technique lies in its space complexity. It uses O(1) extra space since we only need two pointers, regardless of the list’s size. The time complexity is O(n) because in the worst case, we traverse each node at most twice - once to detect the cycle and once to find its starting point. This makes it much more efficient than storing visited nodes in a hashmap.

Fast & Slow pointers are particularly effective for problems involving linked lists. When you see these patterns, consider using this technique: finding cycles, middle elements, or problems requiring splitting lists. The key is recognizing when moving pointers at different speeds can give you useful information about the list’s structure.

The most common variations are same-start problems like cycle detection, and offset-start problems like finding the left-middle node. You can also modify the speed ratio - two steps for finding the middle, three steps for finding the first third, and so on. This flexibility makes the technique powerful for various linked list problems.

Fast & Slow pointers is a powerful technique for solving linked list problems efficiently. These best practices will help you recognize when to use this pattern and implement it effectively: