Fast & Slow pointers pattern: Tortoise and Hare technique for coding interview

Fast & Slow pointers (also called the Tortoise and Hare technique) is a variation of the Two Pointers pattern where two pointers move through the same data structure at different speeds.

Usually:

• slow moves 1 step at a time.
• fast moves 2 steps at a time.

The pattern is especially useful with Linked Lists and cyclic structures, because it can detect properties of the structure using O(1) extra space.

The key idea is:

If two pointers move at different speeds through a cycle, the faster pointer will catch the slower pointer.

Let's imagine two runners on a circular track. One moves twice as fast as the other. Even if the faster runner starts behind, they will eventually meet. This gives us a way to detect a cycle without storing visited nodes. So instead of O(n) additional space, we often get:
Time: O(n)
Space: O(1)

How does Fast & Slow pointers pattern work?

The key movement is:

slow = slow->next;
fast = fast->next->next;

slow moved one node, fast moved two. After more iterations, both pointers are inside the cycle. Since fast gains one node per iteration on slow, eventually slow == fast. That proves a cycle exists.

How to recognize the Fast & Slow pointers pattern

When you read a problem description and see phrases like:

• detect a cycle
• find the middle
• repeated state
• duplicate without extra space

may be you should use Tortoise and Hare technique (Fast & Slow pointers pattern) for solving the problem.

LeetCode problems to learn the Tortoise and Hare technique

141. Linked List Cycle
142. Linked List Cycle II
202. Happy Number
234. Palindrome Linked List
287. Find the Duplicate Number
876. Middle of the Linked List

I recommend 876. Middle of the Linked List as the first problem to study when learning the Fast & Slow pointers pattern.

Here is the simple solution on Java:

class Solution {
  public ListNode middleNode(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    while(fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }

    return slow;
  }
}