Fast and Slow pointers

Question 1

What is the Fast & Slow Pointers pattern and when is it used?

Answer 1

Uses two pointers moving at different speeds to detect cycles or midpoints.

Use Case: Linked list cycles, midpoints, or palindromes.

Question 2

What are the key steps in the Fast & Slow Pointers technique?

Answer 2

1. Initialize slow/fast pointers at head.
2. Move slow by 1, fast by 2 until meet or end.
3. Analyze meeting point (e.g., cycle exists).

Question 3

How does the Fast & Slow Pointers technique apply to Detect Cycle?

Answer 3

Detect cycle in linked list.
Approach: Fast pointer moves twice as fast; meeting indicates cycle.

Question 4

What are the complexity and gotchas of the Fast & Slow Pointers technique?

Answer 4

Time: O(n), Space: O(1).
Gotchas: No cycle, single node.

Question 5

Code example for Fast & Slow Pointers.

Answer 5

```python
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: ‘ListNode’ = None):
self.val = val
self.next = next
def has_cycle(head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
~~~

Question 6

Visual: [Add image manually].