Two Pointer

Fast & Slow (Floyd's)

One pointer moves 1 step, the other moves 2 steps. If there's a cycle, they'll meet. Also finds the middle of a sequence (when fast reaches end, slow is at middle). Key technique for linked list cycle detection.

O(n)

O(1)

How It Works

Floyd's technique runs two pointers through a sequence at different speeds: slow advances one step per iteration, fast advances two. If the sequence contains a cycle, fast eventually laps slow and they meet inside the loop — the gap between them shrinks by one each step, so a meeting is guaranteed. If fast reaches the end, there is no cycle.

The same idea locates the middle of a list: when fast hits the end, slow sits at the midpoint. Compared with hashing every visited node, which needs O(n) memory, Floyd's runs in O(n) time with O(1) space. A second phase — resetting one pointer to the head and stepping both singly — even finds the exact cycle entry.

Step-by-Step Visualization

Linked list: 1→2→3→4→5→back to 3 (cycle)

→3

Slownode 1

Fastnode 1

1/4

Code

Java

static boolean hasCycle(ListNode head) {
  ListNode slow = head, fast = head;

  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true; // Cycle!
  }

  return false; // No cycle
}

// To find cycle start after detection:
// Reset slow to head, move both at speed 1
// They meet at the cycle entrance

Tips & Gotchas

1Fast moves 2 steps, slow moves 1 step per iteration

2If there is a cycle, they WILL meet (pigeonhole principle)

3To find cycle start: reset one pointer to head, move both at speed 1

Practice Problems

1Linked List Cycle
2Linked List Cycle II
3Find the Duplicate Number
4Happy Number
5Middle of the Linked List

About the Two Pointer Pattern

Use two index variables that move through the array strategically. They might start at opposite ends and converge, or both start at the beginning with one moving faster. This avoids nested loops.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

Why does Find the Duplicate Number count as a fast and slow pointer problem on an array?

Treat each index i as a node whose next pointer is nums[i]; a duplicate value means two indices point to the same node, creating a cycle. Floyd's algorithm then finds the cycle entrance, which is the duplicate, in O(n) time and O(1) space without modifying the array.

After the pointers meet, how do I find where the cycle begins?

Move one pointer back to the head and advance both one step at a time; they meet exactly at the cycle's start. This works because the distance from head to entry equals the remaining distance from the meeting point around the loop, a fact that falls out of the 2:1 speed ratio.